hdu 4974 數學雜題/證明

hdu 4974 數學雜題/證明

題意模型：n個正數，每次可以做下面倆種操作之一：

1：取一個數減一。

2：取倆個數各減一。

都必需保證每次操作的數>0.

求使得所有數字為0的最少操作次數。

都說是簡單題，網上還有不少錯誤解法（排序後掃一遍，每次取最大的倆個數減到0： 2 2 2 這樣是4次，正解3次）。

應該是每次取最大的倆個數，各減1.

若maxi>sum/2,則ans=max,每次操作都用那個max,和其他一個數，最後max沒人找了，自己減。

若maxi

#include
#include
using namespace std;
int main()
{
    int T;
   scanf("%d",&T);
    for(int ii=1;ii<=T;ii++)
    {
        int n;
        scanf("%d",&n);
       int sum=0,maxs=-1,cur;
        for(int i=0;imaxs)maxs=cur;
        }
        if(maxs>=(sum+1)/2)
        printf("Case #%d: %d\n",ii,maxs);
        else
        printf("Case #%d: %d\n",ii,(sum+1)/2);
    }
    return 0;
}