2022 Hangzhou Electric Multi-School Training Session 3 1009 Package Delivery

题目链接

Package Delivery

题目大意

给定我们$n$个快递,Each courier has an arrival time and latest pick-up time,We can take at most at a time$k$个快递,Ask us what is the minimum number of trips to the express station？

题解

经典的贪心题,We should make the trolleys that pick up the courier as full as possible each time,So when we go to pick up the courier, it should be the day to pick up the courier on the last day of an item,Because the items accumulated that day should be the most.We first sort by express delivery time,Then take out the latest pick-up time of all couriers and sort them in order,Enumerate latest pickup time,Then operate according to the current accumulated goods,具体细节看代码~

代码

#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;
}