2022杭电杯超级联赛(5)

1012 Buy Figurines

题解：需要两个优先队列，一个优先队列存储 正在购物的人的结束时间和所属队伍编号，另一个优先队列存储队伍信息（队伍编号，人数，最晚结束时间，以及队伍信息编号 信息编号越大表示队伍信息越新，老的队伍信息不可以用，碰到直接删除，保证使用的队伍信息必须是该队伍最新的信息），每个人来的时候，需要先看第一个优先队列 中有没有人要走了，走的话需要更新对应队伍的信息，并将新的队伍信息放到第二个优先队列中，然后再看队伍信息，找到第一个最新的队伍信息，将该人排到该队列后面即可。然后看时间最久的一个人的结束时间即可。

通过优先队列可以快速找到最符合条件的队伍，进而减少时间复杂度。

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
struct student {
     //人
	int a,s;//a 到达时间 s 购物时间
	int time;//结束时间
	int num;//该人在哪只队伍
	bool operator<(const student &a)const {
    
		return time>a.time;
	}
};
student stu[1000006];//保存人的信息
int sum[1000005];//保存各个队伍当前的总人数
bool cmp(student &a,student &b) {
     //按照人到达的时间排序
	return a.a<b.a;
}
struct quq {
     //队伍信息
	int num,idx;//队伍编号 队伍idx
	int sum;//队伍人数
	bool operator<(const quq &a)const {
    
		if(sum!=a.sum)
			return sum>a.sum;//如果人不相等 则人少的排在前面
		if(num!=a.num) {
    
			return num>a.num;//如果人数相等 编号小的在前面
		}
		return idx<a.idx;//如果编号也相等 则表示同一只队伍 则最新的队伍信息--idx大的 在前面
	}
};
priority_queue<quq>q1;//队伍信息的 优先队列
priority_queue<student>st;//正在购物的人员信息的优先队列
ll js[1000006];//记录各个队伍当前最后一名的结束时间
int id[1000005];//记录队伍的最新idx
void solve() {
    
	int n,m;
	while(q1.size())q1.pop();
	while(st.size())st.pop(); 
	memset(js,0,sizeof(js));
	memset(id,0,sizeof(id));
	memset(sum,0,sizeof(sum));
	memset(stu,0,sizeof(stu));
	scanf("%d%d",&n,&m);
	for(int i=0; i<n; i++) {
    
		scanf("%d%d",&stu[i].a,&stu[i].s);
	}
	for(int i=0; i<m; i++) {
    
		quq qu;//初始化m只队伍信息
		qu.num=i;//队伍编号
		qu.idx=0;//队伍idx
		qu.sum=0;//队伍没有人
		q1.push(qu);
	}
	sort(stu,stu+n,cmp);//按照人物到达时间排序 从小到大
	ll ma=0;
	for(int i=0; i<n; i++) {
    
		ll t=stu[i].a;//当前人的到达时间
		while(st.size()) {
    
			student s1=st.top();//正在购物 人的信息
			if(s1.time<=t) {
     // 购物时间到达 则该人应该走了 它所对应的队伍信息需要更新
				st.pop();
				sum[s1.num]--;//对应队伍的人数需要-1
				quq temp;
				temp.sum=sum[s1.num];
				temp.idx=++id[s1.num];//队伍的idx需要+1
				temp.num=s1.num;//队伍的编号
				q1.push(temp);
			} else {
    
				break;
			}
		}
		while(q1.size()) {
    
			quq temp=q1.top();
			if(temp.idx!=id[temp.num]) {
     //如果该队伍已经不是该队伍的最新信息了..
				q1.pop();
			} else {
    
				q1.pop();
				temp.idx=++id[temp.num];//队伍idx+1;
				t=max(t,js[temp.num]);//看人员的真实开始时间
				t+=stu[i].s;
				
				stu[i].time=t;//人员的结束时间
				stu[i].num=temp.num;//人员所在的队伍编号
				st.push(stu[i]); //进入购物
				
				ma=max(ma,t);
				
				js[temp.num]=t;//队伍的结束时间更新
				sum[temp.num]++;//队伍的人数+1
				temp.sum=sum[temp.num];
				
				q1.push(temp);
				break;
			}
		}
	}
	cout<<ma<<'\n';
}
int main() {
    
	int t;
	scanf("%d",&t);
	while(t--) {
    
		solve();
	}
}