「vijos1894」セチの祈り
背景
琼花飘落 彩蝶曼舞 又是一年春
满腹愁情 化作伤春酒
梧桐细雨 影影绰绰 残阳落
韶华飞逝 梦断都成空
描述
在 Ninian 的花园里，有许多琼花，环绕着中间的凉亭。
有 N 片琼花，组成一个环。
Ninian 想在凉亭中发动 [セチの祈り] ， 需要划分出三个区域的琼花，为了平均，要最大化面积最小的区域的面积。
划分区域：即用三刀把这个环分成三段，每段称之为一个区域。
格式
输入格式
第一行一个整数 N 。
接下来 N 个整数 Si ，表示第 i 片琼花的面积。
输出格式
输出一个整数，面积最小的区域的面积。
样例2
限制
对于 20% 的数据：
3 ≤ N ≤ 400
对于 100% 的数据：
3 ≤ N ≤ 100 000
1 ≤ Ai ≤ 1 000 000 000
来源
布吉岛。
题解
二分答案ans+前缀和贪心判定。。。
扫一遍，前i个分为第一组，从最后再找几个放到第一组，即a[n]-a[x-1]+a[i]>=ans，x尽量大，x用二分找
同样i+1到x-1分为两组，再次二分找出分界。。
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans,midans,s[100005]; int n,a[100005]; int find(int l,int r,ll x) { int R=r,t=-1; while(l<=r) { int mid=(l+r)>>1; if(s[R]-s[mid-1]>=x)t=mid,l=mid+1; else r=mid-1; } return t; } bool jud() { for(int i=0;i<=n;i++) { if(midans<s[i])continue; int x=find(i+1,n,midans-s[i]); int y=find(i+1,x-1,midans); if(y==-1)continue; if(s[y-1]-s[i]>=midans)return 1; } return 0; } int main() { n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i]; ll l=0,r=s[n]; while(l<=r) { midans=(l+r)>>1; if(jud())ans=midans,l=midans+1; else r=midans-1; } printf("%lld",ans); return 0; } |
Subscribe
计数器 9787597
OI 课件=>
OI 课件=>