题解 UVA1335 【Beijing Guards】

· · 题解

题意

有n个人围成一个圈，每个人都需要一定数量的礼物，并且相邻两个人手中的礼物种类不能相同，给定每个人所需的礼物数量a_i，求最少需要多少种礼物。

分析

  1. 如果n为偶数，那么答案即为max\{a_i+a_{i+1}\}(1≤i≤n)，规定a_{n+1}=a_1，此时，我们设这个答案为p，则一定可以构造出这样一个合法方案，对于任意一个人，若他的编号i为奇数，则发给他的礼物种类为1 ~ a_i，否则发给他的礼物种类为p-a_i+1 ~ p，可以发现这个方案是符合题目要求的。

  2. 如果n为奇数，这时上述策略就会有问题，因为第n个人会与第1个人冲突，此时，我们考虑二分答案，我们可以发现，答案具有单调性，礼品种类数越大，越能使构造出的合法方案。设我们现在已经二分出一个值x，我们要来验证此时的值时候可以构造出合法方案。我们设第1个人取1~a_1种礼物，那么此时的最优策略一定是编号i为偶数的人尽量往前取，编号i为奇数的人尽量往后取，这样编号为n的人在不冲突的情况下就尽量取了后a_n种礼物，此时如果第n个人还会与第1个人冲突，那么说明x这个值不合法，否则就是合法的。

  3. 所以，现在我们就来考虑如果实现我们的check函数，我们先设l表示第1个人取的礼物种类总数，r表示除第1个人取的礼物以外的礼物种类数，所以l=a_1，r=x-a_1，left[i]表示第i个人拥有的礼物种类在1 ~ a_1间的礼物数量，right[i]表示第i个人拥有的礼物种类在a_1+1 ~ x间的礼物数量，首先left[1]=l，right[1]=0，因为第1个人只取前a_1种礼物。然后，对于编号i为偶数的人，因为他需要尽量往前取，所以left[i]=min\{a_i,l-left[i-1]\}，第一项是这个人最多能取的种类数，第二项是每个人能取的靠前的礼物种类总数减去前一个人取的靠前的礼物种类数，因为这个人不能和前一个人冲突，而right[i]=a_i-left[i]，因为这个人所取的礼物不是在前半段就是在后半段。而编号i为奇数的情况也同理，所以right[i]=min\{a[i],r-right[i-1]\}，left[i]=a_i-right[i-1]，最后若left[n]=0说明情况合法，因为此时最后一个人就与第1个人不冲突了。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,a[N],lf[N],rt[N];
bool check(int x)
{
    int l=a[1],r=x-a[1];
    lf[1]=l;
    rt[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(i%2==0)
        {
            lf[i]=min(a[i],l-lf[i-1]);
            rt[i]=a[i]-lf[i];
        }
        else
        {
            rt[i]=min(a[i],r-rt[i-1]);
            lf[i]=a[i]-rt[i];
        }
    }
    return lf[n]==0;
}
int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        memset(a,0,sizeof(a)); 
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        if(n==1)
        {
            printf("%d\n",a[1]);
            continue; 
        }
        a[n+1]=a[1]; 
        int l=0,r=0;
        for(int i=1;i<=n;i++) l=max(l,a[i]+a[i+1]);
        for(int i=1;i<=n;i++) r=max(r,a[i]*3);
        //答案的下界就是n为偶数的答案，而答案的上界就是当n为3时，三个相同的数
        if(n%2==0)
        {
            printf("%d\n",l);
            continue;
        }
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        printf("%d\n",l);
    } 
    return 0;
}