[SWJTU1705 GreatAccepted]【贪心】

【Link】http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1705

【题目大意】

n个数，你每次可以取<=3个数出来将他们都-1。然后放回去。问将所有数变为0至少需要多少次操作。

输出的两个数中第二个数是Sum

【算法】

lcc大神一下就秒杀了。我完全YY不出来。

 

first of all，每次取最大的3个出来减这种贪心是肯定没问题的。

但是数目太多了。

考虑每次都只能将一个数-1。

所以答案至少是最大那个数。

设m1是最大那个数，m2是次大那个数。

那么看看m1什么时候会将答案卡住。

很容易想到就是每次m1都减，减到最后的情况。然后看剩下的2个名额怎么去减。

用这两个名额，

要么是m2把这个名额卡住了，

要么减到最后剩下一个1，

要么是除了m1全部减为0。

 

(原因可以模拟一开始的贪心看看)

 

后面两种就判一下是不是Sum-m1<=m1*2就可以了。

第一种的卡住，只能发生在m2一直减，减到最后的情况，所以就是Sum-m1-m2<=m2。

 

答案被卡住的情况解决了，剩下的就是没被卡住的情况。

这些情况的答案都是Sum/3向上取整。

还是参见一开始的贪心，现在假设n>3(n<=3必然是答案是m1)每次我们都选最大的3个减。最后因为不会再被m1卡住了。设这些数中最小值为min，容易必然能够转到下面3种情况中的一种。

1、所有数都=min

2、2个数=min，其余数=min+1

3、1个数=min，其余数=min+1

转化为这个以后、、不断的3个3个减。。。很容易知道最后要么刚好减完，要么剩一个1，要么剩2个1。因为都是3个3个减，所以就和它% 3的结果有关系。。。于是就是Sum/3向上取整了= =

【其它】

Orz lcc大神

【CODE】

#include

#include

#include

#include

using namespace std;

 

int main(){

    int Tc,n;

    int a[1005];

    scanf("%d",&Tc);

    for (int k=1;k<=Tc;k++){

        scanf("%d",&n);

        for (int i=0;i

          scanf("%d",&a[i]);

        sort(a,a+n);

        int Sum=0,ans;

        for (int i=0;i

        if (n<=3) ans=a[n-1];

        else

            if (Sum-a[n-1]-a[n-2]<=a[n-2])

                ans=a[n-1];

            else

                if ( Sum-a[n-1]<=a[n-1]*2 )

                  ans=a[n-1];

                else ans=(Sum+2)/3;

        printf("Case #%d: ",k);

        printf("%d %dn",ans,Sum);

    }

}