題目連結：http://codeforces.com/contest/1106/problem/B
題意是有n個菜，m個操作，接下來一行輸入每個菜的盤數，再下來一行輸入每盤菜的價格，接下來m行，每行兩個數分别表示第x個菜，要買y盤，輸出他要支付的價錢，如果第x個菜不夠y盤，他将會去買價格最低的菜，直到買夠y盤，如果所有的菜都賣完了也不夠y盤，他就會不高興，然後帶着那些不夠y盤的菜不給錢就走了。
比較巧妙的思維題，寫法就是按題意分類讨論然後模拟就完了，暴力的去模拟的話，親測TLE，然後這裡需要一個巧妙的轉換，就是開一個id數組，将每盤菜的id按它的價格排序，然後用一個變量去記錄并更新最便宜的菜的位置就好了。說的不太清楚，看呆碼了解吧，不是很難。
AC代碼：
#include <bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
int w[maxn], cnt[maxn], id[maxn];
int n,m;
bool cmp(int x,int y){
return w[x] < w[y];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&cnt[i]);
id[i] = i;
}
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
sort(id + 1, id + n + 1, cmp); // 按價格排序
int pos = 1; // 标記最便宜的菜的位置
while(m--){
int x, y;
scanf("%d%d",&x,&y);
int p = min(cnt[x], y); // 取二者最小值
ll ans = (ll)p * (ll)w[x];
cnt[x] -= p; y -= p;
while(y && pos <= n){ // 如果y有剩餘，進入while循環
if(cnt[id[pos]] == 0) pos++; // 如果第pos便宜的菜賣完了 pos++
p = min(cnt[id[pos]] , y);
ans += (ll)p * (ll)w[id[pos]];
cnt[id[pos]] -= p;
y -= p;
}
if(y == 0) printf("%lld\n", ans);
else puts("0");
}
return 0;
} 複制