专栏文章

题解：P11677 [USACO25JAN] Shock Wave P

ggeorge0929
P11677题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minn1dy7
此快照首次捕获于
2025/12/02 05:05
3 个月前
此快照最后确认于
2025/12/02 05:05
3 个月前
查看原文
首先各种 DP 都没有任何前途。
考虑分析性质减少不必要的操作，对于一个操作 ii，肯定不能断言它能够被其他操作替代，考虑分析两个操作 i,ji,j，发现将操作 i,ji,j 替换为操作 1,n1,n 一定更优。
因此我们最后肯定是先操作若干次 11，再操作若干次 nn，最后操作一次 m (2≤m≤n−1)m\ (2\leq m\leq n-1)。
考虑二分只操作 1,n1,n 的最小操作次数 ansans，然后检查 ans−1ans-1 是否可行。
设 11 操作了 aa 次，nn 操作了 bb 次，不妨设 2i≤n2i\leq n（2i>n2i>n 同理），有如下式子：
pi≤a(i−1)+b(n−i)p_i\leq a(i-1)+b(n-i)
强行提取 ansans 的表达式 a+ba+b。
pi≤(a+b)(i−1)+b(n−2i+1)b≥pi−(a+b)(i−1)n−2i+1p_i\leq (a+b)(i-1)+b(n-2i+1) \\ b\geq \frac{p_i-(a+b)(i-1)}{n-2i+1}
当 2i>n2i>n 时，同理可得：
a≥pi−(a+b)(n−i)2i−n+1a\geq \frac{p_i-(a+b)(n-i)}{2i-n+1}
因此，只需满足 max⁡pi−(a+b)(i−1)n−2i+1+max⁡pi−(a+b)(n−i)2i−n+1≤a+b\max \frac{p_i-(a+b)(i-1)}{n-2i+1}+\max \frac{p_i-(a+b)(n-i)}{2i-n+1}\leq a+b 即可。
因此我们可以轻松求得 ansans，检查 ans−1ans-1 时，我们的式子又多出了一部分。（2i>n2i>n 的情况略）
∃2≤m≤n−1,max⁡pi−(a+b)(i−1)−∣m−i∣n−2i+1+max⁡⋯≤a+b\exist 2\leq m\leq n-1,\max \frac{p_i-(a+b)(i-1)-|m-i|}{n-2i+1}+\max \dots \leq a+b
我们希望对所有 mm 维护一坨式子的最大值。
考虑这个式子的变化次数，∣m−i∣n−2i+1\frac{|m-i|}{n-2i+1} 只会变化不超过 nn−2i+1\frac{n}{n-2i+1} 次，因此总变化量是调和级数的。
实现方面，我们只关心最大的 pi−(a+b)(i−1)−∣m−i∣n−2i+1\frac{p_i-(a+b)(i-1)-|m-i|}{n-2i+1}，考虑让最大值递减，利用可删堆的思想，每次保证最大值更新即可。由于 a,b≥0a,b\geq 0，我们不用处理任何式子是负数的情况。
必须要满足最大值递减才能保证优先队列做法正确，而 mm 增加时只保证 i<mi<m 的最大值递减，因此需要先从小到大枚举 mm，再从大到小枚举 mm，做两遍。
做两遍的时候需要控制优先队列中只保留 i>mi>m 或 i<mi<m 的数，因为多余的数可能无法更新到其本身的最大值，影响答案。
复杂度 O(T(nlog⁡V+nlog⁡2n))O(T(n\log V+n\log^2n))。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p[100005];
bool ck(int ans){
	int blim=0,alim=0,rlim=0;
	for(int i=1;i<=n;i++){
		if(i<=n/2){
			blim=max((__int128)blim,((__int128)p[i]-(__int128)ans*(i-1)+n-2*i)/(__int128)(n-2*i+1));
		}else{
			if(2*i-n-1==0){
				rlim=max(rlim,(p[i]+i-2)/(i-1));
				continue;
			}
			alim=max((__int128)alim,((__int128)p[i]-(__int128)ans*(n-i)+2*i-n-2)/(__int128)(2*i-n-1));
		}
	}
	return alim+blim<=ans&&rlim<=ans;
}
struct node{
	int m,val,i;
	bool operator<(const node &b) const{
		return val<b.val;
	}
};
int lima[100005],limb[100005];
int calca(int ans,int i,int m){
	return ((__int128)p[i]-(__int128)ans*(n-i)+2*i-n-2-abs(m-i))/(__int128)(2*i-n-1);
}
int calcb(int ans,int i,int m){
	return ((__int128)p[i]-(__int128)ans*(i-1)+n-2*i-abs(m-i))/(__int128)(n-2*i+1);
}
bool fullchk(int ans){
	for(int i=1;i<=n;i++) lima[i]=limb[i]=0;
	priority_queue<node> Qb,Qa;
	int nowm=n;
	do{
		while(!Qa.empty()&&Qa.top().m!=nowm&&Qa.top().val!=calca(ans,Qa.top().i,nowm)){
			auto x=Qa.top();
			Qa.pop();
			x.m=nowm;
			x.val=calca(ans,x.i,nowm);
			Qa.push(x);
		}
		while(!Qb.empty()&&Qb.top().m!=nowm&&Qb.top().val!=calcb(ans,Qb.top().i,nowm)){
			auto x=Qb.top();
			Qb.pop();
			x.m=nowm;
			x.val=calcb(ans,x.i,nowm);
			Qb.push(x);
		}
		if(2*nowm-n-1!=0){
			if(nowm<=n/2){
				Qb.push({nowm,calcb(ans,nowm,nowm),nowm});
			}else{
				Qa.push({nowm,calca(ans,nowm,nowm),nowm});
			}
		}
		if(!Qa.empty()) lima[nowm]=Qa.top().val;
		if(!Qb.empty()) limb[nowm]=Qb.top().val;
	}while(nowm--);
	nowm=1;
	while(!Qa.empty()) Qa.pop();
	while(!Qb.empty()) Qb.pop();
	do{
		while(!Qa.empty()&&Qa.top().m!=nowm&&Qa.top().val!=calca(ans,Qa.top().i,nowm)){
			auto x=Qa.top();
			Qa.pop();
			x.m=nowm;
			x.val=calca(ans,x.i,nowm);
			Qa.push(x);
		}
		while(!Qb.empty()&&Qb.top().m!=nowm&&Qb.top().val!=calcb(ans,Qb.top().i,nowm)){
			auto x=Qb.top();
			Qb.pop();
			x.m=nowm;
			x.val=calcb(ans,x.i,nowm);
			Qb.push(x);
		}
		if(2*nowm-n-1!=0){
			if(nowm<=n/2){
				Qb.push({nowm,calcb(ans,nowm,nowm),nowm});
			}else{
				Qa.push({nowm,calca(ans,nowm,nowm),nowm});
			}
		}
		if(!Qa.empty()) lima[nowm]=max(lima[nowm],Qa.top().val);
		if(!Qb.empty()) limb[nowm]=max(limb[nowm],Qb.top().val);
		nowm++;
	}while(nowm<=n);
	for(int i=1;i<=n;i++){
		if(lima[i]+limb[i]<=ans){
			if(n%2==0) return 1;
			else if(p[(n+1)/2]<=(__int128)ans*(n-1)/2+abs(i-(n+1)/2)) return 1;
		}
	}
	return 0;
}
void solve(){
	cin>>n;
	int mx=0;
	for(int i=1;i<=n;i++) cin>>p[i],mx=max(mx,p[i]);
	if(mx==0){
		cout<<"0\n";
		return; 
	}
	int l=0,r=2e18,ans=2e18+1;
	while(l<=r){
		int mid=(l+r)/2;
		if(ck(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	if(ans<=1){
		cout<<"1\n";
		return;
	}
	if(fullchk(ans-2)){
		cout<<ans-1<<"\n";
		return;
	}
	cout<<ans<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...