ABC D求调
  • 板块灌水区
  • 楼主BYR_KKK
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/10/22 09:42
  • 上次更新2023/11/2 12:00:44
查看原帖
ABC D求调
802664
BYR_KKK楼主2023/10/22 09:42

思路贪心,wa*6


#include<bits/stdc++.h>
#define int long long
#define pii std::pair<int,int>
#define fi first
#define se second

const int maxn=2e5+10;

pii a[maxn];

bool cmp(pii x1,pii x2){
	if(x1.fi!=x2.fi) return x1.fi<x2.fi;
	return x1.se<x2.se;
}

signed main(){
	int n;
	std::cin>>n;
	for(int i=1;i<=n;i++){
		std::cin>>a[i].fi;
		int d;
		std::cin>>d;
		a[i].se=a[i].fi+d;
	}
	std::sort(a+1,a+n+1,cmp);
	int ans=0;
	int now=-1;
	for(int i=1;i<=n;i++){
		if(now<a[i].fi) now=a[i].fi+1,ans++;
		else {
			if(now<=a[i].se) now++,ans++;
		}
	}
	std::cout<<ans;
	return 0;
}

2023/10/22 09:42
加载中...