Codeforces Round 973 (Div. 2) D

这篇文章介绍了Codeforces Round 973 (Div. 2) D，分享给大家做个参考，收藏极客之家收获更多编程知识

性质1：题目操作相当于将前面的数搬到了后面，将其视为柱状图，则是把前面柱的高度转移至后面柱的高度
性质2：最后移成的序列以单调不下降序列为最优，易证明当存在下降时，可通过操作使答案更优或不变差
性质3：由于性质2，易得最佳序列尾部最高，故可以通过栈来维护，其为单调栈，栈口最高
性质4：对于确定的总和sum与某个数(组）的出现次数cnt，由性质2得只有可能有 sum / cnt 与 sum / cnt + 1 两种取值，易得出现sum / cnt + 1次数为sum%cnt
性质5：优先用大的数来平衡每次加入且需要平衡的数

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2 * 100010 + 10;
int n;
int T;
int f[N];
struct edge
{
	int val;
	int cnt;
};
stack <edge> st;
signed main()
{
	scanf("%lld",&T);
	while(T--)
	{
		while(!st.empty())st.pop();
		scanf("%lld",&n);	
		edge a;
		for(int i = 1;i <= n;i++)
			scanf("%lld",&f[i]);			
		a.val = f[1];
		a.cnt = 1;
		st.push(a);
		for(int i = 2;i <= n;i++)
		{
			a.val = f[i];
			a.cnt = 1;
			while(  !st.empty() && a.val / a.cnt <= st.top().val / st.top().cnt)
			{
				edge b = st.top();
				st.pop();
				a.val += b.val;
				a.cnt += b.cnt;	
			} 
			edge tt;
			tt.val = a.val / a.cnt * (a.cnt - a.val % a.cnt); 
			tt.cnt =  a.cnt - a.val % a.cnt;
			st.push(tt);
			if(a.val % a.cnt > 0)
			{
				tt.val = (a.val / a.cnt + 1) * (a.val % a.cnt);
				tt.cnt = a.val % a.cnt;
				st.push(tt);
			}
		}
		int mx = st.top().val / st.top().cnt;
		int mn = -1;
		while(!st.empty())
		{
			
			mn = st.top().val / st.top().cnt;
			st.pop();
		}
		
		
		printf("%lld\n",mx - mn);
	}	
	return 0; 
} 

版权声明：本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！