招聘网站咋做,国外极简网站,深圳做网站价比高的公司性,莆田网站建设方法传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个数组aaa#xff0c;你要将其分成四份#xff0c;让这四份中和的最大值−-−最小值最小#xff0c;输出这个最小值。 n≤2e5,ai≤1e9n\le2e5,a_i\le1e9n≤2e5,ai≤1e9
思路#xff1a;
直接枚…传送门
文章目录题意思路题意
给你一个数组aaa你要将其分成四份让这四份中和的最大值−-−最小值最小输出这个最小值。 n≤2e5,ai≤1e9n\le2e5,a_i\le1e9n≤2e5,ai≤1e9
思路
直接枚举不是很好做考虑先枚举中间的位置iii设被划分成的四段和分别是s1,s2,s3,s4s1,s2,s3,s4s1,s2,s3,s4且s1s2,s3s4s1s2,s3s4s1s2,s3s4那么答案就是max(s2,s4)−min(s1,s3)max(s2,s4)-min(s1,s3)max(s2,s4)−min(s1,s3)。由此可知我们要让abs(s2−s1)abs(s2-s1)abs(s2−s1)和abs(s4−s3)abs(s4-s3)abs(s4−s3)都尽可能小用两个指针维护一下就好啦。
// Problem: D - Equal Cut
// Contest: AtCoder - AtCoder Regular Contest 100
// URL: https://atcoder.jp/contests/arc100/tasks/arc100_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const LL inf0x3f3f3f3f3f3f3f3f;
const double eps1e-6;int n;
int a[N];
LL pre[N];LL get(LL a,LL b,LL c,LL d) {return max(a,max(b,max(c,d)))-min(a,min(b,min(c,d)));
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cinn;for(int i1;in;i) scanf(%d,a[i]),pre[i]pre[i-1]a[i];LL ansinf;for(int l0,r1,i1;in;i) {while(l1iabs(pre[l]-pre[i]pre[l])abs(pre[l1]-pre[i]pre[l1])) l;while(r1nabs(pre[r]-pre[i]-pre[n]pre[r])abs(pre[r1]-pre[i]-pre[n]pre[r1])) r;ansmin(ans,get(pre[l],pre[i]-pre[l],pre[r]-pre[i],pre[n]-pre[r]));}printf(%lld\n,ans);return 0;
}
/**/
