考场历程十分艰辛啊。。。
- 第一题没切掉，还浪费了很长时间，就是一个裸的最小生成树，但是因为可恶的distance为关键字莫名其妙查错了10min....
- 本题先乱搞了一下，过了样例
- 然后看第三题，可写性极差
- 回头写此题，写了一个自己看起来是正解的二分（正解就是二分）
- 然后干了两小时第三题
- 第三题毛线分都没有（据说是线段树合并）
旁边的dalao没有干第三题，人家写了俩小时正解...
以后我要是再干那种题我就把bk201头拧掉掉....
（以上为闲扯）
~~~~~~~~~~~~我是分割线~~~~~~~~~
化简题意：给一个圈，圈上的点分配ai个数，相邻点的数字不能有相同的，求最小的数字种数
solution：
首先，乱搞可以搞出来：两两之和的最大值就是答案....然后后来过了样例....
为什么呢？
感性证明一波：两个将军之间一定是不能有相同牌子的，也就是说，两个将军之间的牌子数量和就是两个将军需要的牌子和，而隔一个就可以和前一个有重复。
然后呢？会有这样的情况
很神奇，一个奇数环，应该是3，但是乱搞的是2....
但是，秉承着绝不写正解的宗旨，我回到家继续了乱搞....
于是一篇题解看得我五体投地...
这是对于答案的另一种算法：对于每一种牌子，可以把它看成分给n/2个将军，当这些牌子利用最好时，就是最优解。如果是偶数，那当每个牌子n/2时，就是上述情况。问题就在这个奇环上。
同上，对于每一个牌子，分给这些将军，那么总数就是
Σa[i] /(n/2)
（向上取整）
所以，当环是奇数，判断得到的两个答案的最大值，就是真答案了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int n;
int a[maxn];
int ans;
int sum; int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if(n==)
{
printf("%d",n);
return ;
}
ans=a[]+a[n];
for(int i=;i<n;i++)
{
if(a[i]+a[i+]>ans)
ans=a[i]+a[i+];
}
double summ=sum,nn=n,tem;
tem=ceil(summ/(n/));
if((int)tem>ans)
ans=(int)tem;
printf("%d",ans);
return ;
}
正解见下（完）