uva 1335 Beijing Guards(贪心)

 Beijing Guards

Time limit: 3.000 seconds

题目大意：n个人围成圈，第i个人想要ri种礼物，相邻两个人不能有相同的礼物，问至少需要多少种礼物才可满足所有人的要求。

思路：

人数为偶数的情况就是相邻的两个ri想加的最大值p(很好理解),分配策略为，编号i为奇数的人分配礼物1~ri的礼物。而编号i为偶数的人分配礼物编号为p-ri+1~p。所以一定能避免冲突。

人数为奇数的情况：二分答案，若有p种礼物，第一个人把礼物分成两部分。前半部分为1~r1的礼物。后半部分为p-r1+1~p的礼物。最优策略为。编号为奇数的人优先取后半部分的礼物而偶数的人优先取前半部分的礼物。这样就有效减少了冲突率。如果最后一个人和第一个人礼物没有冲突那么p可行。

详细见代码：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=100010;
//typedef __int64 ll;
int aw[maxn],le[maxn],ri[maxn];
int n;
bool isok(int p)
{
    int x,y,i;

    x=aw[1],y=p-aw[1];
    le[1]=x,ri[1]=0;
    for(i=2;i<=n;i++)
    {
        if(i&1)
        {
            ri[i]=min(aw[i],y-ri[i-1]);
            le[i]=aw[i]-ri[i];
        }
        else
        {
            le[i]=min(aw[i],x-le[i-1]);
            ri[i]=aw[i]-le[i];
        }
    }
    return le[n]==0;
}
int main()
{
    int i,ans,low,hi,mid;

    while(scanf("%d",&n),n)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&aw[i]);
        if(n==1)
        {
            printf("%d\n",aw[1]);
            continue;
        }
        low=hi=0;
        for(i=2;i<=n;i++)
            low=max(low,aw[i-1]+aw[i]);
        low=max(aw[1]+aw[n],low);
        if(n&1)
        {
            for(i=1;i<=n;i++)
                hi=max(hi,3*aw[i]);
            while(low<=hi)
            {
                mid=(low+hi)>>1;
                if(isok(mid))
                {
                    ans=mid;
                    hi=mid-1;
                }
                else
                    low=mid+1;
            }
        }
        else
            ans=low;
        printf("%d\n",ans);
    }
    return 0;
}

uva 1335 Beijing Guards(贪心)

原文：http://blog.csdn.net/bossup/article/details/18603199