[2022 Hangzhou Electric Power Multi-School 5 1012 Questions Buy Figurines] Application of STL

题目描述

输入

输出

样例输入

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

样例输出

7

题意

有npersonal shopping,有m个窗口,Everyone has time to arrive and time to spend,When everyone arrives, they pick a queue with fewer people,If there are two or more teams with the least number of people, the team with the lowest sequence number is selected,When I ask how long it takes, everyone buys it all.

思路

Because this process is a deterministic process,比较清晰,So it's a simulation,As for how to simulate this requires a little skill,If for everyoneO(m)The complexity of querying the length of each queue is too high,So say we can maintain oneset,这个setThe node information inside is the number and label of each queue,Then maintain a priority queue,The information of each node in this priority queue is the time,人的编号,出队/入队,Then it's sorted by time,如果时间相同,Then, queue up according to the first out of the queue and then in the queue,Then there is the simulation process,具体可以看代码

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