网站安全建设申请,wordpress分类树,如何建设企业网站ppt,关键词优化排名公司题干#xff1a;
题目大意#xff1a;
有n个人为成一个圈#xff0c;其中第i个人想要r[i]种不同的礼物#xff0c;相邻的两个人可以聊天#xff0c;炫耀自己的礼物。如果两个相邻的人拥有同一种礼物#xff0c;则双方都会很不高兴#xff0c;问最少需要多少种不同的礼…题干
题目大意
有n个人为成一个圈其中第i个人想要r[i]种不同的礼物相邻的两个人可以聊天炫耀自己的礼物。如果两个相邻的人拥有同一种礼物则双方都会很不高兴问最少需要多少种不同的礼物才能满足所有人的需求假设每种礼物有无限多个。 n100000
解题报告
http://www.cnblogs.com/kickit/p/7619889.html
http://www.bubuko.com/infodetail-645767.html
总之就是偶数个的时候直接贪出相邻两者的最大值就可以。 奇数的时候先单独安排第一个并以这一个为分界线分为左右两个区域部分然后剩下的分奇偶进行安排第奇数个尽量往右安排第偶数个尽量往左安排然后安排到最后一个一定是尽量往右安排的然后我们看这个是否和第一个有冲突就行了如果没有冲突那一定是可以的如果有冲突那一定就是说明我们用的李无数是不够的因为我们这样一定是最优解了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int INF 0x3f3f3f3f;
const int MAX 2e5 5;
int a[MAX];
int L[MAX],R[MAX];
int n;
bool ok(int x) {int la[1],rx-a[1];L[1]a[1];R[1]0;for(int i 2; in; i) {if(i%21) {R[i] min(r-R[i-1],a[i]);L[i] a[i]-R[i];}else {L[i] min(l-L[i-1],a[i]);R[i] a[i]-L[i];}}return L[n]0;//填L[n]0也可以AC但是在这里还是0比较好理解因为L和R这两个数组都不存在为负情况。}
int main()
{while(~scanf(%d,n)) {if(n 0) break;int maxx 0;for(int i 1; in; i) {scanf(%d,ai);maxx max(maxx,a[i]a[i-1]);}maxx max(maxx,a[1]a[n]);if(n 1) {printf(%d\n,a[1]);continue;}else if(n % 2 0) {printf(%d\n,maxx);continue;}int l maxx,r INF;int mid (lr)1;while(l r) {mid (lr)1;if(ok(mid)) r mid;else l mid1;}printf(%d\n,l);}return 0 ;}
