you~~~

題目描述

伴隨著科技的發展，我們的生活也越來越多姿多彩，隨著手機的普及，各種交友軟件也在快速的發展。
小a是個老實人，當然只是自己理解而已，其實小a是個不折不扣的渣男。因為他在有女朋友的同時，還在瘋狂的撒網，利用各種交友軟件尋求更適合自己的伴侶。
小a女朋友當然不是省油的燈，自然了解小a的本性，所以在每次見面時就會翻看小a的軟件記錄，來了解小a近期的狀況，機智的小a當然會在女朋友來之前就給完全清理干凈了。
終于在某次時間緊急的情況下，小a的軟件記錄并不一定能夠完全刪除，但是小a知道，自己每個軟件記錄的火熱程度以及最終刪除時間（即可以刪除的最晚時間，過時將無法刪除）。每個軟件記錄的刪除需要一分鐘，軟件記錄的火熱程度，正好對應著女朋友的刺激值，小a想知道，在有限的時間內，如何才能夠讓女朋友的刺激值最小，求出最小值。

輸入

第一行一個正整數T。表示樣例個數（0 < T < 10）
每組有兩個整數n，m，分別表示一共有n個軟件以及女朋友到來的時間（0 < n <= 10^5,0 < m <= 10^6）
往下對應著n行，每行有兩個正整數e,f分別對應每個軟件記錄的火熱程度和該軟件的最終刪除時間。(0 < e <= 10^5,0 < f <= 10^6)
題目中涉及到的時間全部以分鐘為單位。

輸出

輸出對女朋友的最小刺激值；結果占一行。

樣例輸入

2
4 2
20 1
10 1
30 2
40 2
6 2
20 1
10 1
30 2
40 2
50 3
60 3

樣例輸出

30
100

思路

• 貪心： 時間從后往前找最大的刺激的值。
• 優先隊列，數組模擬超時

AC

#include<bits/stdc++.h> #define ll long long #define mem(a, b) memset(a, b, sizeof(a)) #define N 100005 #define P pair<ll, int> using namespace std; struct ac{ll v, t;//優先隊列中 刺激值降序 bool operator < (const ac &x) const{return x.v > v;} }a[N]; // 時間降序 bool cmp_t (ac x, ac y) {return x.t > y.t; } int main() { // freopen("in.txt", "r", stdin);int t;scanf("%d", &t);while (t--) {priority_queue<ac, vector<ac> >que;int n, m;//sum 總刺激值//ans 先記錄可以消除的刺激值；sum - ans int sum = 0, ans = 0;scanf("%d%d", &n, &m);for (int i = 0; i < n; i++) {scanf("%d%d", &a[i].v, &a[i].t);sum += a[i].v;}sort(a, a + n, cmp_t);int now = 0;//時間從后往前 while (m) {while (now < n && a[now].t >= m) {que.push(a[now]);now++;}//每次去隊列中的最大值 if (!que.empty()) {ans += que.top().v;que.pop();}m--;}ans = sum - ans;printf("%d\n", ans);} return 0; }

總結

以上是生活随笔為你收集整理的2095 : 我只看看不写题（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。