CF1283E.New Year Parties(贪心)1800

2022年6月28日 下午12:52 杂项 ,

题意

题目链接:Problem - E - Codeforces
给你一个长度为n的数组a,每个元素都可以+1或者-1,但只能一次。问最后不同元素的最小值和最大值分别是多少。例如:

7
4 3 7 1 4 3 3

嗯,我先sort一下,这样好看,变成:

7
1 3 3 3 4 4 7

然后通过操作可以变成

2 4 4 4 4 4 8 ->3
1 2 3 4 5 5 6 ->6

思路

看我构造的已经能够看出来了,分为两种情况
1)最小值
最小值可以看出,每次如果能与前面够着(指操作能够相等)那么就尽量去够,比如i=3的时候,发现前面是4,所以也去+1;如果够不着,那么就往后贴,尽量与后面的够着。例如这个i=2的时候,与前面的2够不着,那么就自己+1往后面贴。

2)最大值
最大值的话,还是贪心去找,我对于每个数字尽量往前面贴,如果前面有了就找它下一个,假如第一个数字是2,那么肯定得让2减1让它变成1,这样能够更多的留给后面空间。那么这个时候第二个数字是2怎么办?看到减一之后前面的有数字了(指1),那么我就占2的为止。
那么这个时候第三个数字还是2怎么办?那么就贪心去占3的为止。

代码

inline void Case_Test()
{
    cin>>n;
    ans = 0; pre = -1;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for (int i=1;i<=n;i++)
    {
        if (pre < a[i]-1)
        {
            pre = a[i]+1;
            ans++;
        }
    }
    cout<<ans<<" ";
    ans = 0; pre = -1;
    for (int i=1;i<=n;i++)
    {
        if (pre < a[i] - 1)
        {
            ans++;
            pre = a[i]-1;
        }
        else if (pre == a[i] - 1)
        {
            ans++;
            pre = a[i];
        }
        else if (pre == a[i])
        {
            ans++;
            pre = a[i]+1;
        }
    }
    cout<<ans;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注