本文主要是介绍AtCoder - 4167 Equal Cut(2分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://arc100.contest.atcoder.jp/tasks/arc100_b?lang=en
二分 ；
因为要切3刀，我们先枚举中间的刀。
然后二分两边的刀，让两边的2部分尽量相等，算一个答案，每次枚举就会得到一个答案。
取最小即可。
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long int
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
const int inf = 0x3f3f3f3f;
long long a[222222];
long long pre[222222];
long long roo[222222];
int main()
{int n;while (cin >> n ){for (int i = 0; i < n; i++)cin >> a[i];long long ans = -1;pre[0] = a[0];roo[n - 1] = a[n - 1];for (int i = 1; i < n; i++)pre[i] = pre[i - 1] + a[i];for (int i = n - 2; i >= 0; i--)roo[i] = roo[i + 1] + a[i];for (int i = 1; i <= n - 3; i++){long long ls = pre[i] ;long long rs = roo[i + 1];long long l1, l2, r1, r2;long long lz = lower_bound(pre, pre + i + 1, ls / 2)-pre;if (lz != 0)lz--;l1 = pre[lz];l2 = ls - l1;long long rz = lower_bound(pre, pre + n, ls + rs / 2) - pre;if (rz != i + 1)rz--;r1 = pre[rz] - pre[i];r2 = rs - r1;long long zs = max(l1, max(l2, max(r1, r2)));zs = abs(zs - min(l1, min(l2, min(r1, r2))));if (ans == -1 || ans > zs)ans=zs;l1 = pre[lz + 1];l2 = ls - l1;r1 = pre[rz] - pre[i];r2 = rs - r1;zs = max(l1, max(l2, max(r1, r2)));zs = abs(zs - min(l1, min(l2, min(r1, r2))));if (ans == -1 || ans > zs)ans = zs;l1 = pre[lz + 1];l2 = ls - l1;r1 = pre[rz+1] - pre[i];r2 = rs - r1;zs = max(l1, max(l2, max(r1, r2)));zs = abs(zs - min(l1, min(l2, min(r1, r2))));if (ans == -1 || ans > zs)ans = zs;l1 = pre[lz];l2 = ls - l1;r1 = pre[rz+1] - pre[i];r2 = rs - r1;zs = max(l1, max(l2, max(r1, r2)));zs = abs(zs - min(l1, min(l2, min(r1, r2))));if (ans == -1 || ans > zs)ans = zs;}cout << ans << endl;}return 0;
}
这篇关于AtCoder - 4167 Equal Cut(2分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
