题目传送门:Problem - 7170 (hdu.edu.cn)
题意 / Problem
有N个包裹,可以在[l, r]的时间内去取,一次最多取k个,问最少取多少次可以取完所有包裹。
思路 / Thought
贪心的思想,确实很难想,但是题目做多了也容易想到,区间先排序。
将区间分两种方法排序,a数组根据r排序,b数组根据排序。
为使得取包裹次数尽可能少,就应该每次取包裹时间尽可能晚(因为这样可以使得每次取得的包裹尽可能达到k个),但是又一定要取到第一个包裹,所以每次取r最小的那个包裹(从前往后遍历a数组),并且在b数组中将l <= 最小的r的所有包裹都加入到队列里(注意只有b数组的元素入队),然后从队列中取出r最小的k个包裹,并标记为已经取走了,往下遍历a时遇到取走的就跳过。
这里可能会遇到一个问题:每次从队列中取走k个,有没有可能队列里还剩下一些包裹,后面会取不出来呢?不会的,因为a数组会遍历完,最坏的情况就是每次取一个,按照a中的顺序取。
利用双指针和优先队列可以完成以上操作。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; typedef pair<int, int> PII; const int maxn = 1e5 + 9, MAXL = 55; int N, K; struct Node { int l, r, id; }a[maxn], b[maxn]; bitset<maxn> del; bool cmpl(Node &u, Node &v){return u.l < v.l;} bool cmpr(Node &u, Node &v){return u.r < v.r;} struct cmp { bool operator ()(const PII &a, const PII &b)const { return a.first > b.first; } }; void solve() { del.reset(); cin >> N >> K; for(int i = 1;i <= N; ++ i) { cin >> a[i].l >> a[i].r; a[i].id = i; b[i] = a[i]; } sort(a + 1,a + 1 + N, cmpr); sort(b + 1,b + 1 + N, cmpl); priority_queue<PII, vector<PII>, cmp> pq; int ans = 0; for(int i = 1, j = 1;i <= N; ++ i)//每次选择r最小的 { if(del[a[i].id])continue;//如果已经拿走了就跳过 while(j <= N && b[j].l <= a[i].r)//将可以拿走的都放到队列里 { pq.push({b[j].r, b[j].id}); ++ j; } ans ++; for(int t = 1;t <= K && !pq.empty(); ++ t)//每次选 r 最小的 k 个拿走 { del[pq.top().second] = true; pq.pop(); } } cout << ans << '\n'; } signed main() { ios::sync_with_stdio(false); int _;cin >> _; while(_ --)solve(); return 0; }
Comments NOTHING