我只看看不写题 ( 优先队列 )-摩杜云开发者社区

题目描述

伴随着科技的发展，我们的生活也越来越多姿多彩，随着手机的普及，各种交友软件也在快速的发展。

小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)

题目中涉及到的时间全部以分钟为单位。

输出

输出对女朋友的最小刺激值；结果占一行。

样例输入

复制

样例输出

复制

30
100

思路：

模拟，先求得 n 个软件最晚删除时间 Max；

vector <int> a[1000100] , a[i] 存储的是第 i 秒可以删除的软件。

时间从 1 -> m, 如果第 i 秒不删除软件，那么就将这次机会累积，可以删除之后的软件；

如果第 i 秒可以删除的软件删不完，如果这一秒剩余的软件的火热程度大于之前的已经删除的软件，就代替那个软件被删除。

时间 m+1 -> Max 。如果当前的软件的火热程度大于之前的已经删除的软件，就代替那个软件。

#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;
priority_queue <int, vector<int>, greater<int> > Q;// int型降序优先队列

vector <int> a[1000100];
int main()
{
    int T;
    cin >> T;
    while(T--) {
        int n, m;
        cin >> n >> m;
        
        int e, f, Max = 0;
        long long ans = 0;
        
        for(int i=1; i<=n; i++) {
            scanf("%d %d",&e, &f);
            if(f > Max) Max = f; 
            ans += e;
            a[f].push_back(e);
        }

        int times = 0;
        for(int t=1; t<=m; t++) {
            times ++;

            int len = a[t].size();
            if(0 == len) continue;

            if(len <= times) {
                times -= len;
                for(int j=0; j<len; j++) {
                    Q.push( a[t][j] );
                }
            }
            else {
                sort(a[t].begin(), a[t].end());
                
                for(int k=1; k<=times; k++) {
                    Q.push(a[t][len-k]);
                }
                for(int k = times+1; k<=len; k++) {
                    if(a[t][len-k] > Q.top()) {
                        Q.pop();
                        Q.push(a[t][len-k]);
                    }
                    else break;
                }
                times = 0; 
            }
            a[t].clear();
        }
        
        for(int t=m+1; t<=Max; t++) {
             int len = a[t].size();
            if(0 == len) continue;

            if(len <= times) {
                times -= len;
                for(int j=0; j<len; j++) {
                    Q.push( a[t][j] );
                }
            }
            else {
                sort(a[t].begin(), a[t].end());
                
                for(int k=1; k<=times; k++) {
                    Q.push(a[t][len-k]);
                }
                for(int k = times+1; k<=len; k++) {
                    if(a[t][len-k] > Q.top()) {
                        Q.pop();
                        Q.push(a[t][len-k]);
                    }
                    else break;
                }
                times = 0; 
            }
            a[t].clear();
        }

        while(!Q.empty()) {
            ans -= Q.top();
            Q.pop();
        }
        cout << ans << endl;
    }
    return 0;
}