CF-1013-E1. Canteen (Easy Version)

思路讲解

其实也是自己琢磨琢磨出来的，当然不好好写复盘大抵是看不懂以前自己的思路的。

FOR(i,0,N-1){
	diff[i]=B[i]-A[i];
}
ll ans=1;
// diff是负值表示需要调和

就是直接模拟肯定TLE，但是可以退而求其次，**一个一个模拟。**在这个需调和块遇到其他的需调和块之前，不用担心操作有后效性。在碰到其他调和块之后，让他先开路，如果他变成0了，再变成你了。

当然可能碰到多个调和块，这个时候就是使用栈来维护，一个为0弹出1个，换后面一个，直到处理完这个最初的，弹出。

AC代码

https://codeforces.com/contest/2089/submission/316959785

源代码

// Problem: E1. Canteen (Easy Version)
// Contest: Codeforces - Codeforces Round 1012 (Div. 2)
// URL: https://codeforces.com/contest/2090/problem/E1
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
// constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,K,T,A[MAXN],B[MAXN];
ll diff[MAXN];

inline ll mod(ll x){
	ll res=(x-1)%N;
	if(res<0) res+=N;
	return res;
}

inline void solve(){
	cin>>N>>K;
	// 0-based
	bool all0=true;
	for(int i=0;i<N;++i){
		cin>>A[i];
		if(A[i]!=0) all0=false;
	}
	if(all0){
		cout<<0<<"\n";
		return;
	} 
	FOR(i,0,N-1){
		cin>>B[i];
	}
	FOR(i,0,N-1){
		diff[i]=B[i]-A[i];
	}
	ll ans=1;
	// diff是负值表示需要调和
	FOR(i,0,N-1){
		if(diff[i]>=0) continue;
		ll idx=i;
		ll cnt=1;
		vector<ll> labs;
		labs.pb(i);
		while(diff[i]<0){
			++idx;
			++cnt;
			idx%=N;
			if(idx<0) idx+=N;
			
			if(diff[idx]>=0){
				// 现在需要处理的最后一个labs
				assert(!labs.empty());	// 保险一下，断言这个东西不为空，我RE也知道哪里RE
				ll lab=labs.back();
				diff[lab]+=diff[idx];
				diff[idx]=0;
				if(diff[lab]>0){
					// 这个情况其实是diff[idx]>=0的情况
					// 就是没减干净，所以说idx也要停一下，cnt也要停一下
					diff[idx]+=diff[lab];
					diff[lab]=0;
					if(lab!=i) --cnt;
					// lab=upLab;
					--idx;
					labs.pop_back();  // 起到lab=upLab的作用
					//--ltot;	// 起到lab=upLab的作用
					// if(ltot<0) break;
				} 
				// if(lab==i) ++cnt;
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}else{
				labs.pb(idx);
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}
		}
		ans=max(ans,cnt);
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://codeforces.com/contest/2089/submission/316959785

*/

心路历程（WA，TLE，MLE……）

这段代码会造成这个死循环，虽然说比较隐蔽，但这个死循环的罪魁祸首就是upLab。

这个upLab和lab如果相同的会导致lab=upLab 这句话出现问题，并不起到作用。

死循环代码

		ll idx=i;
		ll lab=i;
		ll cnt=1;
		// vector<ll> labs;
		ll upLab=-1;
		while(diff[i]<0){
			++idx;
			++cnt;
			idx%=N;
			if(idx<0) idx+=N;
			
			if(diff[idx]>=0){
				diff[lab]+=diff[idx];
				diff[idx]=0;
				if(diff[lab]>0){
					diff[idx]+=diff[lab];
					diff[lab]=0;
					if(lab!=i) --cnt;
					lab=upLab;
					--idx;
				} 
				// if(lab==i) ++cnt;
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}else{
				upLab=lab;
				lab=idx;
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}
		}

这个代码过了5个点，但还是有点问题，怀疑是因为我这个算法没有去真实的记录每个点的实际抵消所需操作数，现在看起来要改一改了，确保这个每个点的抵消所需操作数都被真实记录。

但好像也不太对，就是我们都是把这个碰到的 $diff<0$ 的点搞到 $≥0$ 才罢休，而且这个也会记录到最初的点当中

https://codeforces.com/contest/2089/submission/316947463

错误代码

// Problem: E1. Canteen (Easy Version)
// Contest: Codeforces - Codeforces Round 1012 (Div. 2)
// URL: https://codeforces.com/contest/2090/problem/E1
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
// constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,K,T,A[MAXN],B[MAXN];
ll diff[MAXN];

inline ll mod(ll x){
	ll res=(x-1)%N;
	if(res<0) res+=N;
	return res;
}

inline void solve(){
	cin>>N>>K;
	// 0-based
	bool all0=true;
	for(int i=0;i<N;++i){
		cin>>A[i];
		if(A[i]!=0) all0=false;
	}
	if(all0){
		cout<<0<<"\n";
		return;
	} 
	FOR(i,0,N-1){
		cin>>B[i];
	}
	FOR(i,0,N-1){
		diff[i]=B[i]-A[i];
	}
	ll ans=1;
	// diff是负值表示需要调和
	FOR(i,0,N-1){
		if(diff[i]>=0) continue;
		ll idx=i;
		ll ltot=0;
		ll cnt=1;
		vector<ll> labs;
		labs.pb(i);
		while(diff[i]<0){
			++idx;
			++cnt;
			idx%=N;
			if(idx<0) idx+=N;
			
			if(diff[idx]>=0){
				ll lab=labs[ltot];
				diff[lab]+=diff[idx];
				diff[idx]=0;
				if(diff[lab]>0){
					diff[idx]+=diff[lab];
					diff[lab]=0;
					if(lab!=i) --cnt;
					// lab=upLab;
					--idx;
					--ltot;	// 起到lab=upLab的作用
					if(ltot<0) break;
				} 
				// if(lab==i) ++cnt;
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}else{
				// lab=idx;
				++ltot;
				labs.pb(idx);
// #ifdef LOCAL
    // cerr<<"lab:" << lab<<" cnt:"<<cnt<<" idx:"<<idx << '\n';
// #endif
			}
		}
		ans=max(ans,cnt);
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*


*/

事实证明我的猜想是对的，只是ltot这个东西就有问题，直接改成栈，把这个ltot优化掉了就好了