题解：P13959 [ICPC 2023 Nanjing R] 计数器

由于操作只有清零和加一，所以对于每个

i

，第

a_i-b_i

次操作是清零，

a_i-b_i+1

到

a_i

的操作都是加一。

如果一个加一的区间里面在后来说要清零，那么肯定输出 No。

用映射记录每个加一的左开右闭区间，然后排序（STL 的 map 是自动排序的）。两个区间左端点相同的，是合法的，因为都一起清零，但是这样，右端点要取最大值。

遍历所有区间，如果两个区间冲突，即一个区间左端点小于等于上一个区间左端点,那么输出 No。如果没有区间冲突，输出 Yes。

code

CPP

#include <bits/stdc++.h>
using namespace std;
map<int,int> a;
void c(){
	a.clear();
	int n,m;
	cin>>n>>m;
	while(m--){
		int x,y;
		cin>>x>>y;
		a[x-y]=max(a[x-y],x);
	}
	int r=-1;
	for(pair<int,int> i:a){
		if(i.first<=r){
			cout<<"No\n";
			return;
		}
		r=i.second;
	}
	cout<<"Yes\n";
}
int main(){
	int T;
	cin>>T;
	while(T--){
		c();
	}
}

题解：P13959 [ICPC 2023 Nanjing R] 计数器

文章操作

code

相关推荐

评论

题解：P13959 [ICPC 2023 Nanjing R] 计数器