披萨

题目描述

Kikok 得到了一块比萨，他迫不及待地想与妹妹 Kik 子和 koko 美一同享用它。 比萨是一种圆形的食物。为了将它分给三个人，Kikok 需要沿着半径方向切三刀。可是，由于这个比萨太硬了，Kikok 只能沿着划好的刀痕把它切开。比萨上一开始有 n 条刀痕，沿顺时针将它们按照从 1到 n 的顺序标号

当 1≤i≤n 时，第 i 条刀痕与第 i+1 条刀痕之间的部分大小为 ai；第 n 条与第 1 条刀痕之间的部分大小为 an

因为怕妹妹们哭闹，在比萨分成三块后，Kikok 准备让妹妹们拿较大的两块，自己拿最小的一块

可是，Kikok 实在太喜欢比萨了，他想吃地尽可能多，也就是让切出的比萨中最小的一块尽可能地更大。那么，Kikok 最多能吃到多少比萨呢？

输入格式

输入文件第一行包含一个整数 n，表示比萨上刀痕的数量。

接下来 n 行，其中第 i 行包含一个整数 ai，依次表示相邻两条刀痕之间的部分的大小。

输出格式

输出一行一个整数，表示最小的一块比萨的最大大小。

样例

Input 1:

6

1 5 4 5 2 4

Output 1:

6

今天考试的第二题www，没有复习集训的内容，导致我看到这道第一想法是：我要爆搜！！！ 除了想到维护三个指针外就想不到其他的了（果然是我太弱了）。

后来在讲题的时候，LSY大佬说了二分法，在下一下就懂了（这题原来这么水） 然后用static是因为把它定义成静态。（详情见度娘）（其实没用）

以下就是代码啦~~~

#include
#include
#include
using namespace std;
int main()
{int n;scanf("%d", &n);static int a[1000005];long long aa = 0;for(int i = 0;i < n;i++){scanf("%d", a + i);aa += a[i];}
long long l = 0, r = aa + 1;
while(l + 1 < r)
{long long mid = (l + r) / 2;static long long s[1000005];static int p[1000005];for(int i = 0;i < n;i++){if(i > 0){p[i] = p[i - 1] - 1;s[i] = s[i - 1] - a[i - 1];}else{p[i] = 0;s[i] = 0;}while(s[i] < mid){s[i] += a[(i + p[i]) % n];p[i]++;}}bool b = 0;for(int i = 0;i < n;i++)if(aa - s[i] - s[(i + p[i]) % n] >= mid)b = 1;if(b) l = mid;else r = mid;
}//二分printf("%lld\n", l);return 0;//完美收关
}

转载于:https://www.cnblogs.com/jiqimin/p/10628222.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！