P1208 [USACO1.3]混合牛奶 Mixing Milk
思路分析
求最小花费需要从最小单价的奶农那里开始采购，依次递增，直到达到乳业的需求量；可以定义两个数组 p[ ] 和 a[ ]， 分别存放每个奶农的单价和产量，通过快速排序算法根据单价从小到大排序；最后可以通过一个循环计算乳业的最小花费；
注意事项
由题可知：对于100%的数据：0 <= n, ai <= 2*10^6, 0 ≤ m <= 5000, 0 <= pi <=1000；所以数组定义为p[5000], a[5000]；对数组进行排序操作时，p[ ] 和 a[ ] 必须一一对应；每天乳业可以从奶农手中采购到小于或者等于奶农最大产量的整数数量的牛奶。防止采购量多出需求量导致花费增加；
代码实现
#include <stdio.h>
void Swap(int*, int*);
void QuickSort(int*, int*, int, int);
int main(){
int n
, m
, i
, M
= 0, S
= 0;
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
);
}
