占领城市

时间：2020-01-28 14:55:30 收藏：0 阅读：72

https://codeforces.com/contest/1283/problem/E

题意：n个人位于1-n坐标上，每一个人可以向左或向右移动一步或不移动。坐标范围为0-n+1.

问这些人最少可以占领多少个坐标，最多可以占领多少个坐标。

解法：最少：i ， i+1 ， i+2 .坐标上的人可以聚集到i+1上来。

最多：将大于1个人的坐标上的人向两边分散开来。

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF  0x3f3f3f3f
#define mod 1000000007
#define PI acos(-1)
using namespace std;
typedef long long ll ;
int a[200009];

int main()
{
    int n ;
    scanf("%d" , &n);
    for(int i = 0 ; i < n ; i++)
    {
        int x ;
        scanf("%d" , &x);
        ++a[x] ;
    }
    int mi = 0 , ma = 0;
    for(int i = 1 ; i <= n ;)
    {
        if(a[i]) i += 3 , mi++;
        else i++;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(a[i] > 1) a[i]-- , a[i+1]++ ;
    }
    for(int i = n ; i >= 1 ; i--)
    {
        if(a[i] > 1) a[i]-- , a[i-1]++;
    }
    for(int i = 0 ; i <= n + 1 ; i ++)
    {
        if(a[i]) ma++;
    }
    cout << mi << " " << ma << endl;

    return 0 ;
}

原文：https://www.cnblogs.com/nonames/p/12238036.html