2022杭电多校训练第三场 1009 Package Delivery

题目链接

Package Delivery

题目大意

给定我们$n$个快递，每个快递有一个到达时间和最晚取快递时间，我们一次最多可以取$k$个快递，问我们去快递站的最小次数是多少？

题解

经典的贪心题，我们应该让取快递的小车每次尽可能装满快递，所以我们去取快递的时候应该是在某个物品的最后一天取快递那天，因为那天积攒的物品应该是最多的。我们先按照快递快递到达时间排个序，然后把所有快递的最晚取货时间拿出来排个序，枚举最晚取货时间，然后根据当前积攒的货物进行操作，具体细节看代码~

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define x first
#define y second
#define int long long
#define endl '\n' 
const int inf = 1e9 + 10;
const int maxn = 100010, M = 2000010;
const int mod = 1e9 + 7;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
int h[maxn], e[M], w[M], ne[M], idx;
int dx[4] = {
    -1, 0, 1, 0}, dy[4] = {
    0, -1, 0, 1};
int cnt;
PII a[maxn];
void add(int a, int b, int c)
{
    
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void add(int a, int b)
{
    
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
signed main()
{
    
    IOS;
    int t; cin >> t;
    while(t --)
    {
    
    	int n, k; cin >> n >> k;
        vector<int> ed;
    	for(int i = 0; i < n; i ++) {
    
            int x, y; cin >> x >> y;
            a[i] = {
    x, y};
            ed.push_back(y);
        }
    	sort(a, a + n);
    	sort(ed.begin(), ed.end());
        priority_queue<int, vector<int>, greater<int>> heap;
        int res = 0, now = 0;
    	for(auto x : ed) {
    
            int cnt = 0;
            while(now < n && a[now].x <= x) heap.push(a[now ++].y);
            while(heap.size() && heap.top() == x) cnt ++, heap.pop();
            res += cnt / k;
            if(cnt % k == 0) continue;
            int extra = k - cnt % k;
            while(heap.size() && extra -- ) heap.pop();
            res ++;
        }
        cout << res << endl;
    }
    return 0;
}