[USACO24FEB] Milk Exchange G
来源
题目描述
Farmer John 的 N(11≤N≤5⋅10^5)头奶牛排成一圈。第 i 头奶牛有一个容量为整数 ai(1≤ai≤10^9)升的桶。所有桶初始时都是满的。
每一分钟,对于 1≤i<N,奶牛 ii 会将其桶中所有牛奶传递给奶牛 i+1,奶牛 N 将其牛奶传递给奶牛 1。所有交换同时发生(即,如果一头奶牛的桶是满的,送出 x 升牛奶同时收到 x 升,则她的牛奶量保持不变)。如果此时一头奶牛的牛奶量超过ai,则多余的牛奶会损失。
在 1,2,…,N 的每一分钟后,所有奶牛总共还余下多少牛奶?
输入格式
输入的第一行包含 N。
第二行包含a1,a2,…,aN。
输出格式
输出 N行,其中第 i行包含 i分钟后所有奶牛总共余下的牛奶量。
思路
奶牛是按排成一圈的,常规套路可以把数组复制几遍方便处理。容易想到把最小的放到最左边,可以在右移的过程中把右边的给覆盖掉,在研究的时候可以更直观得看出来。
下面是一个样例的示例图:
在这里可以直观地看出来,每一个数字形成的图形是有规律的,大致是三角形或者是平行四边形。这里我门考虑每一个数字在每一行产生的贡献,比如第六的数字2,在第一行到第四行产生的贡献是2,4,6,8,在第四行到第五行是不变的,在第五行到第八行的贡献是8,6,4,2。其它的形状也可以用类似概括,可以发现这是一个递增的等差数列(公差为ai),一个不变的等差数列(公差为0),一个递减的等差数列(公差为-ai),对于一段区间,累加上一段等差数列,知道了首项和公差,我们可以用两次差分,前缀和实现。
比如:要实现的等差数列是a1,a1+d,a1+2d,a1+3d
第一次要达到的是a1,d,d,d,d(做一次前缀和即可实现上面)
这里就能明显地看出来这些同样的d可以用基础的差分前缀和实现。
至于三个数列的起始点和终止点,可以用两次单调栈维护每个数字左右第一次小于它的数字。然后直接手推三个关系式子即可。
add(1,min(i-l[i],r[i]-i),a[i],a[i]);
add(min(i-l[i],r[i]-i)+1,max(i-l[i],r[i]-i),(min(i-l[i],r[i]-i))*a[i],0);
add(max(i-l[i],r[i]-i)+1,r[i]-l[i]-1,(min(i-l[i],r[i]-i))*a[i]-a[i],-a[i]);
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
const int N = 5e5 + 10;
int p[N*2],s[N*2],a[N*3],l[N*3],r[N*3],q[N*3],cnt;
inline void add(int l1,int r1,int x,int y){ //维护二阶差分
if(r1<l1){
return;
}
p[l1]+=x;
p[r1+1]-=y*(r1-l1)+x;
s[l1+1]+=y;
s[r1+1]-=y;
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n*2]=a[i];
a[i+n]=a[i];
r[i]=3*n+1;
}
for(int i=1;i<=n*3;i++){
while(cnt&&a[q[cnt]]>=a[i]){
cnt--;
}
l[i]=q[cnt];
q[++cnt]=i;
}
cnt=0;
for(int i=n*3;i>=1;i--){
while(cnt&&a[q[cnt]]>a[i]){
cnt--;
}
if(cnt){
r[i]=q[cnt];
}
q[++cnt]=i;
}
for(int i=1;i<=n;i++){
l[i]=max(l[i+n],i)-n;
r[i]=min(r[i+n],i+2*n)-n;
add(1,min(i-l[i],r[i]-i),a[i],a[i]);
add(min(i-l[i],r[i]-i)+1,max(i-l[i],r[i]-i),(min(i-l[i],r[i]-i))*a[i],0);
add(max(i-l[i],r[i]-i)+1,r[i]-l[i]-1,(min(i-l[i],r[i]-i))*a[i]-a[i],-a[i]);
}
for(int i=1;i<=n;i++){
s[i]+=s[i-1];
p[i]+=s[i];
}
for(int i=2;i<=n;i++){
p[i]+=p[i-1];
cout<<p[i]<<'\n';
}
cout<<p[n];
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin>>T;
while (T--)solve();
return 0;
}
原文地址:https://blog.csdn.net/xinchu0309/article/details/140391617
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!