P2107神奇代码加特判错误,但去掉反而对了,求调
查看原帖
P2107神奇代码加特判错误,但去掉反而对了,求调
801159
RH233楼主2024/7/24 19:13

做题看题解时看见第一篇题解这一行

if(tim > m)//返还所有时间,但是仍然超过了m 
	break;//别走了,再走也没时间AK了

发现自己没有考虑到这种情况,遂加特判,发现WA#11,去掉后却对了,求大佬解释

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e6+10;
ll n,p=1,ans,sum,m;
struct node{
	ll t1,t2;
}a[N];
bool cmd(node x,node y){
	if(x.t1!=y.t1) return x.t1<y.t1;
	return x.t2<y.t2;
}
priority_queue<ll> Q;
signed main(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		cin>>a[i].t1>>a[i].t2;
	}
	sort(a+1,a+1+n,cmd);
	for(ll i=1;i<=n;i++){
		sum+=a[i].t1-a[i-1].t1;
		Q.push(a[i].t2);
		sum+=a[i].t2;
		if(sum>m){
			sum-=Q.top();
			Q.pop();
		}else{
			ans++;
		}
		if(sum>m) break;//特判,把这一行删掉就对了,否则WA#11 
	}
	cout<<ans;
	return 0;
}
2024/7/24 19:13
加载中...