欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【NOIP模拟赛】food

程序员文章站 2023-12-26 07:59:03
...

【NOIP模拟赛】food
题解:把草和牛放在一起存再根据价格排序,然后再从小到大判断,如果是牛就存鲜美程度,不是就在已有牛中查找鲜美程度最接近的那个小于

#include<bits/stdc++.h>
using namespace std;
struct oo{
	long long p,x;
	bool flag;
}cg[200005];
int n,m;
long long ans;
multiset<long long>wm;
int read(){
	int num=0;
	char ch=getchar();
	while(ch>'9'||ch<'0'){
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		num=(num<<1)+(num<<3)+ch-'0';
		ch=getchar();
	}
	return num;
}
bool cmp(oo a,oo b){
	if(a.p==b.p) return a.x<b.x;
	return a.p<b.p;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		cg[i].p=read(),cg[i].x=read(),cg[i].flag=1;
	}
	for(int i=1;i<=m;i++){
		cg[i+n].p=read(),cg[i+n].x=read();
	}
	sort(cg+1,cg+m+n+1,cmp);
	wm.insert(1000000);
	for(int i=1;i<=n+m;i++){
		if(cg[i].flag){
			wm.insert(cg[i].x);
		}
		else{
			if(wm.size()>1&&cg[i].x>=(*wm.begin())){
				set<long long>::iterator x=wm.upper_bound(cg[i].x);
				x--;
				wm.erase(x);
				ans+=cg[i].p;
			}
		}
	}
	if(wm.size()>1){
		puts("-1");
		return 0;
	}
	printf("%lld",ans);
}

上一篇:

下一篇: