题目
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1178
题意
圆桌上有n个人，每个人要求a_i种不同的礼物，相邻两个人的礼物不能重复，问有至少要准备多少种礼物
思路
如刘书
1. 明显，若n=1，直接输出a[0]
2. 若n为偶数，则可以形如ABABAB，直接取最大的两个相连之和
3. 若n为奇数，则可以转化为二分判断问题。
但如何判断x种礼物能否满足要求呢？n * r状态约为1e10，明显太大不能承受。
假设送第0个人,0~a[0]-1这a[0]种礼物，那么第n-1个人明显不能再拿到这a[0]种礼物了。
要找到一个贪心的原则，
由于第n-1个人编号为偶数，那么，偶数的人尽量取a[0]~x-1这些礼物，奇数的人尽量取0~a[0]-1这些礼物就可以。
但是这样如果记录每个状态时还是会出现麻烦。
那么，直接令r[i]记录第i个人拿到0~a[0]-1范围内礼物的数目，l[i]为a[0]~x-1这些礼物的数目，就能记录其状态的同时保持计算传递。
感想
1. 一开始没有注意到如果是奇数，如ABABA这种情况就会挨在一起了
2. 后来没有想到可以在延展过程中逐渐替换掉一小部分结果，而是以为要直接找个第三个最小元素的换掉，这样结果就太大了
3. 最后是没有注意到特例n=1的存在。
代码
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
const int MAXN = 1e5 + ;
int a[MAXN];
int r[MAXN], l[MAXN];
int n;
bool check(int kindNum) {
int rlimit = a[];
int llimit = kindNum - rlimit;
r[] = rlimit;
l[] = ;
for (int i = ; i < n; i++) {
if (i & ) {
r[i] = min(rlimit - r[i - ], a[i]);
l[i] = a[i] - r[i];
if (l[i] > llimit - l[i - ]) {
assert(false);
return false;
}
}
else {
l[i] = min(llimit - l[i - ], a[i]);
r[i] = a[i] - l[i];
if (r[i] > rlimit - r[i - ]) {
assert(false);
return false;
}
}
}
return r[n - ] == ;
} int main() {
#ifdef LOCAL_DEBUG
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
//freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
for (int ti = ; scanf("%d", &n) == && n; ti++) {
int ans = ;
for (int i = ; i < n; i++) {
scanf("%d", a + i);
if (i)ans = max(ans, a[i] + a[i - ]);
}
ans = max(ans, a[n - ] + a[]);
if (n == ) ans = a[];
else if (n & ) {
int mxAns = * ans + ;
while (ans < mxAns) {
int mid = (ans + mxAns) >> ;
if (check(mid)) {
mxAns = mid;
}
else {
ans = mid + ;
}
}
}
printf("%d\n", ans); } return ;
}