暴力92pts求调
查看原帖
暴力92pts求调
1025171
elainya_stars楼主2025/7/28 10:54

贪心求调

(我这是怎么只 MLE 一个点的)

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=1e5+5;
int n;
struct dp
{
	int d,p;
	bool friend operator<(dp x,dp y) {return x.p>y.p;}
}a[N];

main()
{
	scanf("%lld",&n);
	int tmax=0;
	for(int i=1;i<=n;i++)
	  scanf("%lld%lld",&a[i].d,&a[i].p),tmax=max(tmax,a[i].d);
	bool vis[tmax+2]={};
	sort(a+1,a+n+1);
	int pos=LLONG_MAX-10,ans=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i].d!=a[i-1].d)
		  pos=a[i].d-1;
		while(pos>0 && vis[pos])
		  pos--;
		if(!vis[pos])
		  ans+=a[i].p,vis[pos]=1;
	}
	return !printf("%lld\n",ans);
}
2025/7/28 10:54
加载中...