current position:Home>(5) BuyFigrines Hd 2022 school training

(5) BuyFigrines Hd 2022 school training

2022-08-06 08:54:13ThXe

有n个人m个窗口,Give everyone the time they arrive and the time they need to spend at the window,When everyone arrives, they will choose a queue with a smaller number of people,If the number of people is the same, choose the team with the smaller team number to queue,Ask what time the last person left.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
struct people {
     int arrival, spent; }people[N];//The time everyone arrives and the time it takes
struct Timeline {
    
	ll time; int type, id;//0The representative has previously dealt with the need to leave 1代表未处理
	Timeline(ll _time = 0, int _type = 0, int _id = 0) :
		time(_time), type(_type), id(_id) {
    }
	// type = 0 for departure, type = 1 for arrival
	bool operator < (const Timeline& t) const {
    
		if (time != t.time) return time > t.time;//Spend time for the first keyword Whether to leave the second keyword sorted from largest to smallest
		return type > t.type;
	}
};
priority_queue<Timeline> Tl;//Priority queues maintain everyone's timeline
struct Queue {
    
	int num, id;//The current size of the team 、队伍编号
	Queue(int _num = 0, int _id = 0) :
		num(_num), id(_id) {
    }
	bool operator < (const Queue& t) const {
    
		if (num == t.num) return id < t.id;//Number of people is the first keyword,The number is sorted by the second keyword 从小到大排序
		return num < t.num;
	}
}q[N];//q为n个队伍
set<Queue> Que_set;
int T, n, m, Queue_select[N];
ll ans, Last[N];
int main() {
    
	// freopen("test.in", "r", stdin);
	// freopen("test.out", "w", stdout);
	scanf("%d", &T);
	while (T--) {
    
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; ++i)
			scanf("%d%d", &people[i].arrival, &people[i].spent);//people 存放人的信息,Maintenance timeline
		for (int i = 1; i <= n; ++i)
			Tl.push(Timeline(people[i].arrival, 1, i));//
		Que_set.clear();
		for (int i = 1; i <= m; ++i) {
    
			q[i].num = 0, q[i].id = i;//当前时间为0 编号为i
			Que_set.insert(q[i]);//放入set中
			Last[i] = 0;//记录iThe time end time of the queue
		}
		while (!Tl.empty()) {
    
			auto tl = Tl.top(); Tl.pop();
			ll time = tl.time; int type = tl.type, id = tl.id;//the arrival time of the person、Arrival Type、编号
			if (type == 0) {
    //If leaving the team
				int qid = Queue_select[id];//Release the current team
				Que_set.erase(Queue(q[qid].num, q[qid].id));
				Que_set.insert(Queue(--q[qid].num, q[qid].id));
			}
			else {
    //到达它的l时
				auto que_begin = *Que_set.begin();//Take the first team:The current time is the shortest and the number is the smallest
				int num = que_begin.num, qid = que_begin.id;
				Que_set.erase(que_begin);//Remove this team from the team collection,重新赋值
				Queue_select[id] = qid;//Maintains the team number selected by the current person
				if (num == 0) Last[qid] = time + people[id].spent;//If the team is empty is the start+花费时间
				else Last[qid] += people[id].spent;//Add its cost directly
				q[qid].num++; que_begin.num++;
				Que_set.insert(que_begin);//重新赋值
				Tl.push(Timeline(Last[qid], 0, id));//Put in an end time person
			}
		}
		ans = 0;
		for (int i = 1; i <= m; ++i) ans = max(ans, Last[i]);
		printf("%lld\n", ans);
	}

	return 0;
}
/* 1 4 2 1 2 1 4 2 3 3 5 */


copyright notice
author[ThXe],Please bring the original link to reprint, thank you.
https://en.chowdera.com/2022/218/202208060847342211.html

Random recommended