题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1863
题意：n 个将军驻扎成一个圆，第 i 个将军要求得到\(a_i\) 枚不同颜色的勋章，如果两个相邻的将军拥有颜色相同的勋章会立即造反，问至少需要几种勋章。
二分答案的思路还是比较容易想到的... 不过怎么判断呢...
题解做法比较机智 dp 维护两个数组 f[i]/g[i] 表示第 i 个将军与第 1 个将军重复勋章的最小/最大值
由于是 dp 过来的 一定合法 只需要判断 f[n] 是否等于 0 即可
转移还是不困难的...
|
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 |
#include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iomanip> #include <iostream> #include <algorithm> #define N 100010 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } int a[N],f[N],g[N],n,ans,sum; bool check(int x) { f[1]=g[1]=a[1]; for(int i=2;i<=n;i++) { g[i]=min(a[i],a[1]-f[i-1]); f[i]=max(0,a[1]+a[i-1]+a[i]-g[i-1]-x); } return f[n]==0; } int main() { n=read(); for(int i=1;i<=n;i++) { a[i]=read();sum+=a[i]; ans=max(ans,a[i]+a[i-1]); } int l=ans,r=sum; while(l<=r) { int mid=(l+r)>>1; if(check(mid))r=mid-1; else l=mid+1; } printf("%d",l); return 0; } |
Comments | NOTHING