题意
可以参见LRJ白书第一章例题16.
有n个人，围个圈，每个人想要一定数量的礼物，注意每个人所持礼物不可以重样，两个相邻的人所持的礼物也不能重样，问你至少要准备多少种不同的礼物，才能符合要求？
思路
大概是个构造题综合二分答案。
首先要想到对n的分类讨论：
- 如果n是偶数，那么你只需要准备两套不同配置的礼物，按照ABABABABAB这样循环下去就可以满足要求了，因此答案是max{r_i+r_((i+1)%n)}
- 如果n是奇数，情况就比较复杂。我们可以先反向思考，如果给定有r种礼物，如何才能构造合适的礼物配置满足题设要求？白书里面给了这样一种方法：令编号为奇数的尽量选取靠前的种类，编号为偶数的尽量选取靠后的种类，即把r种礼物分成两半（即前、后两组），对于每一个人维护他按照上面策略进行选取的前组后组中元素数量，最后检查第一个人和最后一个人是否相容即可。这样我们就有了二分答案的检查方法了。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; const int MAXN = 100005; int n; int seq[MAXN]; int ls[MAXN],rs[MAXN]; int res; bool check(int k) { int lb = seq[1],rb = k-lb; ls[1] = seq[1],rs[1] = 0; for(int i = 2; i<= n; i++){ int lrm = lb - ls[i-1]; int rrm = rb - rs[i-1]; if(i % 2 == 0){ if(seq[i] < lrm){ ls[i] = seq[i]; rs[i] = 0; }else{ ls[i] = lrm; rs[i] = seq[i] - lrm; } }else{ if(seq[i] < rrm){ rs[i] = seq[i]; ls[i] = 0; }else{ rs[i] = rrm; ls[i] = seq[i] - rrm; } } } return ls[n] == 0; } int solve() { int l = res,r = 300005,mid; while(l + 1 < r){ int mid = l + (r-l)/2; if(check(mid)){ r = mid; }else{ l = mid+1; } } if(check(l)){ return l; }else { return r; } } int main() { while(scanf(" %d",&n) != EOF && n) { if(n == 1){ scanf(" %d",&n); printf("%d\n",n); continue; } for(int i = 1; i <= n; i++) { scanf(" %d",&seq[i]); } res = 0; for(int i = 1; i <= n; i++) { if(i == n) { res = max(res,seq[1]+seq[n]); } else { res = max(res,seq[i]+seq[i+1]); } } if(n % 2) { printf("%d\n",solve()); } else { printf("%d\n",res); } } return 0; } |
