P2107特判反而错误,求解释
查看原帖
P2107特判反而错误,求解释
801159
RH233楼主2024/7/24 19:34

在看完第一篇题解后,发现这样两行

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

看完后发现没有考虑到,于是加了特判,提交时93pts,后看讨论版,发现要取最大值,修改后再加入特判,又93pts。后来删掉特判反而对了,并发现不取最大值也可以拿100pts,求调

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e6+10;
ll n,p=1,ans,sum,m,ak;
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{
			ak++;
		}
		if(sum>m) break;//神奇的特判 
		ans=max(ans,ak);//可有可无的取最大值 
	}
	cout<<ans;
	return 0;
}

总之就是很神奇,求大佬解释

2024/7/24 19:34
加载中...