题意

给学生发礼物, 学生的桌子排成一行, 要求每个学生发两个礼物, 一种普通礼物, 一种特殊礼物(随意), 要求相邻的普通礼物不能相同

思路

每个学生准备两个礼物, 记礼物总数为sum, 则至多能分给sum/2个学生.

贪心 : 为保证相邻的普通礼物不同, 故尽可能多的放数量多的礼物, 中间插空放数量少的礼物, 当只剩一种礼物且上一次放的就是这个礼物的时候, 不能再继续放礼物, 贪心结束.

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define mst(a) memset(a, 0, sizeof a)using namespace std;const int maxn = 10+5;const int INF = 0x3f3f3f3f;int a[maxn];bool cmp(int a, int b){    return a > b;}int main(){    int T, n, sum, x, all;    int kase = 0;    scanf("%d",&T);    while(T--){        sum = 0, all = 0;        scanf("%d",&n);        for( int i = 0; i < n; i++ ){            scanf("%d",&a[i]);            all += a[i];        }        if( n == 1 && all >= 2 ){            printf("1\n");            continue;        }        else if( all < 2 ){            printf("0\n");            continue;        }        sort(a, a+n, cmp);        int flag = 1;        int i;        int remain = n;        while( sum < all/2 ){            if( flag ){  //取大                i = 0;                while( a[i] == 0 ){                    i++;                }                a[i]--;                if( a[i] == 0 ) remain--;            }            else{                i = n-1;                while( a[i] == 0 ){                    i--;                }                a[i]--;                if( a[i] == 0 ) remain--;            }            sum++;            if( remain == 1 && flag ) break;            flag = !flag;            //printf("%d ",sum);        }        printf("Case #%d: %d\n",++kase,sum);    }    return 0;}