[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;
}