[TIOJ] 1440. 誰買早餐

題目連結:http://tioj.infor.org/problems/1440
因為本題保證:營養越高價錢越高,而且都只剩下一份,所以可以直接把所有食物都按照價錢或營養價值排好序,然後也把每個人需要的營養排序,然後直接$O(m)$掃過去找最小且符合條件的,然後加起來
#include <stdio.h>
#include <algorithm>
typedef long long lld;

using std::sort;

struct food{
	int price, value;
};
int people[1000000 + 10];
food breakfast[1000000 + 10];

inline bool cmp(food a,food b){
	return a.price<b.price;
}

int main(){
	int n,m;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&people[i]);
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d",&breakfast[i].value);
		scanf("%d",&breakfast[i].price);
	}
	sort(people,people+n);
	sort(breakfast,breakfast+m,cmp);
	lld ans=0;
	int pointer=0;
	for(int i=0;i<m;i++){
		if(breakfast[i].value>=people[pointer]){
			ans+=breakfast[i].price;
			pointer++;
			if(pointer>=n)break;
		}
	}
	if(pointer < n)
		puts("Impossible.");
	else
		printf("%lld",ans);
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1902. 「殿仁.王,不認識,誰啊?」,然後他就死了……

[AtCoder] [經典競程 90 題] 024 - Select +/- One(★2)

[AtCoder] [經典競程 90 題] 022 - Cubic Cake(★2)