UVALive 3177 长城守卫

绝地灬酷狼 2022-09-27 13:29 3阅读 0赞

/\*\*  
  
题意: 有n(1<=n<=100 000)个人围成一个圈,  其中第i个人想要r\[i\](1<= r\[i\] <= 100 000)个礼物;

求要使任意相邻的两个人没有相同礼物的最小总礼物数

Sample Input :  
  
5  
2 2 2 2 2  
  
sample Outpu:  
  
5

分析 :  
  
n为偶数时很简单 : ans = max(r\[i\] + r\[i+1\]);  
  
n为奇数时比较棘手:  
既然求最值,试试二分  
那对于给定答案怎样确定是否符合条件呢?  
  
对于给定的礼物数q,设第一个人的礼物为1~r1  
最优分配方案:编号为奇数的人尽量往后取,编号为偶数的人尽量往前取  
  
将其按a\[0\]分为两部分:左部分a\[0\]个,右部分q-a\[0\]个;  
然后i为奇数的人尽量取左边,偶数i尽量取右边.  
若最后一个人一个左部分的都没有取到,则符合条件,  
否则不符合条件  
  
要怎么记录取值呢?  
两个数组,left\[i\]记录取左边的个数,right\[i\]记录取右边的个数

\*/

#include <bits/stdc++.h>
    #define scf(n) scanf("%d",&n)
    #define cao(n) cout<<n<<endl;
    #define mes(a,b)  memset(a,b,sizeof(a))
    using namespace std;
    
    typedef long long ll;
    
    const double eps = 1e-14;
    const long long inf = 1e9 + 7;
    const long long INF = 1e18 + 7;
    
    int a[100100];
    int n;
    int lef[100100];//第i个人拿左部分的个数
    int rig[100100];//第i个人拿右部分的个数
    bool check(int q)
    {
        memset(lef, 0, sizeof(lef));
        memset(rig, 0, sizeof(rig));
        int x = a[1],y = q - a[1];
        lef[1] = x;
        rig[1] = 0;
        //按a[0]分两部分:左边x个和右边y个
        //若第n个人取左边的个数为0 则ok;
        for(int i = 2; i <= n; i++)
        {
            if(i & 1)//尽量拿右边的
            {
                rig[i] = min(y - rig[i-1], a[i]);
                lef[i] = a[i] - rig[i];
            }
            else //尽量拿左边的
            {
                lef[i] = min(x - lef[i-1], a[i]);
                rig[i] = a[i] - lef[i];
            }
        }
        return lef[n] == 0;
    }
    
    int main()
    {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        while(scf(n) != EOF && n)
        {
            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]); //最小值
            if(n & 1)
            {
                for(int i = 1;  i <= n; i++) R = max(R, 3 * a[i]); //最大值
                while(L < R)
                {
                    int mid = (L + R) / 2;
                    if(check(mid)) {R = mid;}
                    else {L = mid + 1;}
                }
            }
            printf("%d\n", L);
        }
        //fclose(stdin);
        //fclose(stdout);
        //freopen("CON","r",stdin);
        //freopen("CON","w",stdout);
        return 0;
    }