求要使任意相邻的两个人没有相同礼物的最小总礼物数
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; }
