0pts 求助||WA||算法:堆||悬首解关
查看原帖
0pts 求助||WA||算法:堆||悬首解关
746930
NO_OI_NO_LIFE楼主2024/1/5 21:34

暴力代码能拿20pts,开了数组反而WA一片

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

int x,n,tot;

struct node{//先按照价格从小到大排序,如果价格一样,就排序保质期天数 
	int pri,day,num;
	bool operator<(const node &rhs) const{
		if(rhs.pri==pri)
			return rhs.day<day;
		return rhs.pri<pri;
	}
}szx[100005];//szx20100828 is kankanxia //废话 

priority_queue<node> pq;

signed main(){
	cin>>x>>n;
	for(int i=1;i<=n;i++){
		cin>>szx[i].pri>>szx[i].day>>szx[i].num;
		pq.push(szx[i]);
	}
	int ans=0;int u=1;bool ok=0;
	for(int i=1;i<=x;i++){
		if(u>n){//如果枚举完了就输出-1 
			cout<<-1<<endl;
			ok=1;
			break;
		}
		if((szx[u].day>=i)&&(--szx[u].num>=0))//如果可以就加价格 
			ans+=szx[u].pri;
		else{//如果过期了或用完了就重新并枚举下一个 
			i--;
			u++;
		}
	}
	if(!ok) cout<<ans<<endl;
	return 0;
}
2024/1/5 21:34
加载中...