Description
湫湫減肥
越減越肥!
最近,減肥失敗的湫湫為發洩心中郁悶,在玩一個消滅免子的游戲。
游戲規則很簡單,用箭殺死免子即可。
箭是一種消耗品,已知有M種不同類型的箭可以選擇,並且每種箭都會對兔子造成傷害,對應的傷害值分別為Di(1 <= i <= M),每種箭需要一定的QQ幣購買。
假設每種箭只能使用一次,每只免子也只能被射一次,請計算要消滅地圖上的所有兔子最少需要的QQ幣。
Input
輸入數據有多組,每組數據有四行;
第一行有兩個整數N,M(1 <= N, M <= 100000),分別表示兔子的個數和箭的種類;
第二行有N個正整數,分別表示兔子的血量Bi(1 <= i <= N);
第三行有M個正整數,表示每把箭所能造成的傷害值Di(1 <= i <= M);
第四行有M個正整數,表示每把箭需要花費的QQ幣Pi(1 <= i <= M)。
特別說明:
1、當箭的傷害值大於等於兔子的血量時,就能將兔子殺死;
2、血量Bi,箭的傷害值Di,箭的價格Pi,均小於等於100000。
Output
如果不能殺死所有兔子,請輸出”No”,否則,請輸出最少的QQ幣數,每組輸出一行。
Sample Input
3 3 1 2 3 2 3 4 1 2 3 3 4 1 2 3 1 2 3 4 1 2 3 1
Sample Output
6 4
思路:在可以殺死兔子的箭中找最小花費的,用到了優先隊列,隨便復習下寫法
#include#include #include #include #include using namespace std; const int MAXN = 100005; struct Node { int D,P; }node[MAXN]; int arr[MAXN], n, m; bool cmp1(Node a, Node b) { return a.D < b.D; } struct cmp { bool operator() (int x, int y) { return x > y; } }; priority_queue , greater > q; int main() { while (scanf("%d%d", &n, &m) != EOF) { while (!q.empty()) q.pop(); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); for (int i = 0; i < m; i++) scanf("%d", &node[i].D); for (int i = 0; i < m; i++) scanf("%d", &node[i].P); if (n > m) { printf("No\n"); continue; } sort(arr, arr+n); sort(node, node+m, cmp1); int cnt = m-1; int flag = 1; long long ans = 0; for (int i = n-1; i >= 0; i--) { while (cnt >= 0 && node[cnt].D >= arr[i]) { q.push(node[cnt].P); cnt--; } if (q.empty()) { flag = 0; break; } ans += q.top(); q.pop(); } if (flag) cout << ans << endl; else cout << "No" << endl; } return 0; }