【2022杭电多校5 1012题 Buy Figurines】STL的运用

题目描述

输入

输出

样例输入

1
5 3
2 4
1 3
5 1
3 4
4 2

样例输出

7

题意

有n个人去买东西，有m个窗口，每个人都有到达时间和花费时间，每个人到的时候都是挑一条人少的队排，如果有两个以上的队人最少的话就挑序号最小的队排，问多少时间的时候所有人全部买完。

思路

因为这个过程是确定性的过程，比较清晰，所以就是个模拟题，至于怎么模拟这个就需要点技巧了，如果对于每一个人都O(m)的查询每个队列的长度的话那么复杂度就太高了，所以说我们可以维护一个set，这个set里面的节点信息是每个队列的人数和标号，然后再维护一个优先队列，这个优先队列里面的每一个节点信息是时间，人的编号，出队/入队，然后是按照时间来排的，如果时间相同，那么按照先出队后入队来排，然后就是模拟的过程了，具体可以看代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
typedef long long LL;
typedef pair<int,int> PII;
struct Que{
    
	LL tim;
	int id,status;
	bool operator<(const Que&t)const{
    
		if(tim == t.tim) return status > t.status;
		return tim > t.tim;
	}
	Que(LL a=0,int b=0,int c=0):tim(a),id(b),status(c){
    }
};
struct mdui{
    
	LL num;
	int id;
	bool operator<(const mdui&t)const{
    
		if(num == t.num) return id < t.id;
		return num < t.num;
	}
	mdui(LL a=0,int b=0):num(a),id(b){
    }
};
mdui q[N];
priority_queue<Que> que;
PII data[N];
set<mdui> dui;
LL last[N];
int Queselect[N];
void solve(){
    
	dui.clear();
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
    
		scanf("%d%d",&data[i].first,&data[i].second);
		que.push(Que(data[i].first,i,1));
	}
	for(int i=1;i<=m;i++){
    
		last[i] = 0;q[i].id = i;q[i].num = 0;
		dui.insert(q[i]);
	}
	while(que.size()){
    
		auto t = que.top();que.pop();
		LL tim = t.tim;
		int id = t.id,status = t.status;
		if(t.status == 0){
    
			int x = Queselect[id];
			dui.erase(mdui(q[x].num,q[x].id));
			dui.insert(mdui(--q[x].num,q[x].id));
		}
		else{
    
			auto x = *dui.begin();
			dui.erase(x);
			if(x.num == 0) last[x.id] = tim + data[id].second;
			else last[x.id] += data[id].second;
			q[x.id].num ++,x.num++;
			Queselect[id] = x.id;
			dui.insert(x);
			que.push(Que(last[x.id],id,0));
		}
	}
	LL ans = 0;
	for(int i=1;i<=m;i++) ans = max(ans,last[i]);
	printf("%lld\n",ans);
}
int main(){
    
	int _;
	scanf("%d",&_);
	while(_--) solve(); 
	return 0;
}