题目属于贪心的分类,我们当然可以按照贪心的一般思路,按照价格的高低首先进行从小到大的排序,然后进行选择。但是有必要进行排序吗?我们可以直接根据价格进行循环啊,题目给出了最大的价格,我们只需要进行这么一次循环,比较剩余的需要需要量和当前价格所对应的牛奶量进行比较,然后简单计算即可!
/* ID: acmerfi1 PROG: milk LANG: C++ */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 5005 #define maxPrice 1000 int sumAmount = 0, sumFamer, sumPrice = 0, priceAmount[maxPrice][1]; int price, amount; int main() { freopen("milk.in", "r", stdin); freopen("milk.out", "w", stdout); memset(priceAmount, 0, sizeof(priceAmount)); scanf("%d%d", &sumAmount, &sumFamer); for(int i = 0; i < sumFamer; i++) { scanf("%d%d", &price, &amount); priceAmount[price][0] += amount; } for(int j = 0; j <= maxPrice; j++) { if(sumAmount >= priceAmount[j][0]) { sumPrice += priceAmount[j][0] * j; sumAmount -= priceAmount[j][0]; } else { sumPrice += sumAmount * j; sumAmount = 0; } if(0 == sumAmount) break; } printf("%d\n", sumPrice); return 0; }