New Year Parties

题意

n个人分布在一维坐标上，每个人可以左走一步xi-1，右走一步xi+1，或者原地不动xi，求通过此操作，最少占用坐标的点数和最多占用的点数分别是多少？

分析

求最小值：

因为最多只能将连续3个坐标的人，放在一个坐标上，所以从左往右扫描，如果i位置上有人，那么i,i+1,i+2就可以住一个房子，结果+1，然后i = i+3，继续同样的操作

求最大值：

从整体出发，先从左往右扫一遍，如果某个位置非空，但是左一个为空，就派一个人去占位，再从右往左扫描，如果某个位置非空，但是右边一个为空，就派一个人去占位。

所以整体上就形成了，整体尽量往左走一个，然后再整体尽量往右走一个，这样就更加能占更多位置

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6+10;

int N,resmin,resmax;
int mp[maxn];
int main(){
    cin>>N;
    int tmp;
    for(int i = 0;i<N;i++){
        scanf("%d",&tmp);
        mp[tmp]++;
    }
    for(int i = 1;i<=N;){
        if(mp[i]){
            resmin++;
            i = i+3;
        }else i++;
    }
    for(int i = 1;i<=N;i++){
        if(!mp[i-1] && mp[i]) mp[i-1]++,mp[i]--;
    }
    for(int i = N;i>=1;i--){
        if(!mp[i+1] && mp[i]) mp[i+1]++,mp[i]--;
    }
    for(int i = 0;i<=N+1;i++) if(mp[i]) resmax++;
    cout<<resmin<<" "<<resmax<<endl;
    return 0;
}