P1208 [USACO1.3]混合牛奶 Mixing Milk——题解2020.10.1

P1208 [USACO1.3]混合牛奶 Mixing Milk

思路分析

• 求最小花费需要从最小单价的奶农那里开始采购，依次递增，直到达到乳业的需求量；
• 可以定义两个数组 p[ ] 和 a[ ]， 分别存放每个奶农的单价和产量，通过快速排序算法根据单价从小到大排序；
• 最后可以通过一个循环计算乳业的最小花费；

注意事项

• 由题可知：对于100%的数据：0 <= n, ai <= 2*10^6, 0 ≤ m <= 5000, 0 <= pi <=1000；所以数组定义为p[5000], a[5000]；
• 每天乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。防止采购量多出需求量导致花费增加；

代码实现

#include <stdio.h>
void Swap(int*, int*);
void QuickSort(int*, int*, int, int);//快速排序;
int main(){
    int n, m, i, M = 0, S = 0;//M表示花费金额, S表示采购量;int p[5000], a[5000];scanf("%d%d", &n, &m);for(i = 0; i < m; i++){
    scanf("%d%d", &p[i], &a[i]);}QuickSort(p, a, 0, m-1);for(i = 0; i < m; i++){
    S += a[i];//采购量不能大于需求量;if(S > n){
    S -= a[i];break;}M += p[i] * a[i];}//将采购量和需求量的差值补齐;if(S < n)M += p[i] * (n - S);printf("%d", M);return 0;
}
void Swap(int *p, int *q){
    int t;t = *p;*p = *q;*q = t;return;
}
void QuickSort(int *p, int *a, int low, int high){
    int i = low;int j = high;int key = p[low];if (low >= high)return ;while (low < high){
    while (low < high && key <= p[high])--high;if (key > p[high]){
    Swap(&p[low], &p[high]);Swap(&a[low], &a[high]);++low;}while (low < high && key >= p[low])++low;if (key < p[low]){
    Swap(&p[low], &p[high]);Swap(&a[low], &a[high]);--high;}}QuickSort(p, a, i, low-1);QuickSort(p, a, low+1, j);
}