|
试题描述
|
|
JOI 君马上要和妹妹 JOI 子和 JOI 美一起吃小吃。今天的小吃是他们三个人都很喜欢的年轮蛋糕。 年轮蛋糕是像下图一样呈圆筒形的蛋糕。为了把蛋糕分给三个人，JOI 君必须沿着半径方向切 3 刀，从而把蛋糕分成三块。然而，由于年轮蛋糕硬得像实木一样，要让刀切进去并不简单。因此，这个年轮蛋糕上事先准备了 N 个切口，而 JOI 君只能在有切口的位置下刀。切口按顺时针顺序编号为 1到 N，对于 1≤i≤N−1，第 i 个切口和第 i+1个切口之间部分的大小是 Ai。第 N 个切口和第 1个切口之间部分的大小是 AN 。
图 1：一个年轮蛋糕的例子，N=6,A1=1,A2=5,A3=4,A4=5,A5=2,A6=4 妹控的 JOI 君在把蛋糕切成 3 块之后，自己选走最小的一块吃掉，把剩下两块分给两个妹妹。而另一方面，JOI 君太喜欢年轮蛋糕了，只要能吃到的时候就会想吃很多很多。试求：最小块的大小不超过多少。 样例说明 1
图 2：从第 1,3,5个切口下刀时是最优解（即图中粗实线位置）。 |
|
输入
|
|
从标准输入读入以下内容：
• 第 1 行有一个整数 N，表示年轮蛋糕上有 N 个切口； • 接下来有 N 行，第 i(1≤i≤N)行有一个整数 Ai，表示第 i 个切口和第 i+1 个切口之间部分（当 i=N 时即为第 N 个和第 1 个之间部分）的大小。 |
|
输出
|
|
输出到标准输出，仅一行一个整数，表示当把年轮蛋糕切成 3 块之后最小块大小的最大值。
|
|
输入示例
|
|
输入样例 1
6 1 5 4 5 2 4 输入样例 2 30 1 34 44 13 30 1 9 3 7 7 20 12 2 44 6 9 44 31 17 20 33 18 48 23 19 31 24 50 43 15 |
|
输出示例
|
|
输出样例 1
6 输出样例 2 213 |
国庆Day2 T1
考场很Sb的写了一个二分套二分，被卡飞了，所以说我们来看一看是怎么写的
首先是二分答案 （从0到sum/3）
然后我们用两个二分来求出右边刚好大于二分出来的值的下标
然后判断是否可行
代码fo常好写，然后来看怎么优化，首先是每次只要求出来就return
然后我们已知在枚举左端点的时候，与之对应的右端点是递增的
所以我们可以记录上一次求出的下标作为本次二分的左边界
时间复杂度差不多是O(nlogsum*常数)
大概要跑700多
然后最重要的就是，开long long
下面给出代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdio> #include<cstring> #include<string> #include<cmath> using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; return x*f; } inline void write(long long x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return ; } int n; int a[100006]; long long sum[200006]; long long l=0,r=3; inline bool check(long long x){ int f=0; int la1=0,la2=0; int mid; for(register int i=1;i<=n;i++){ int ll=i,rr=i+n-1; if(la1) ll=la1; int set=0; int num=0; while(ll<=rr){ mid=(ll+rr)>>1; if(sum[mid]-sum[i-1]>=x) num=mid,rr=mid-1; else ll=mid+1; } set=num; la1=num; ll=set+1,rr=i+n-1; if(la2) ll=la2; if(sum[set]-sum[i-1]<x) continue; while(ll<=rr){ mid=(ll+rr)>>1; if(sum[mid]-sum[set]>=x) num=mid,rr=mid-1; else ll=mid+1; } if(sum[num]-sum[set]<x) continue; la2=rr; if(sum[i+n-1]-sum[num]<x) continue; f=1; break; } return f; } int main(){ n=rd(); for(register int i=1;i<=n;i++){ a[i]=rd(); sum[i]=sum[i-1]+(long long)a[i]; r+=a[i]; } for(register int i=n+1;i<=n*2;i++) sum[i]=sum[i-1]+(long long)a[i-n]; r/=3; long long ans=0; while(l<=r){ long long mid=(l+r)>>1; if(check(mid)) ans=mid,l=mid+1; else r=mid-1; } write(ans); return 0; }