引入:结构体排序
结构体排序的两种方式:1、**结构体内部重载运算符** 2、**重写cmp函数**
结构体重载运算符<
struct Order
{
int t;
int id;
bool operator<(const Order&a)const
{
if (t!=a.t) return t<a.t;
else return id<a.id;
}
}order[N];
重写cmp函数
bool cmp(const Order&a,const Order&b) //a是否应该排在b的前面,如果是,就返回true,否则返回false
{
if (a.t!=b.t) return a.t<b.t;
else return a.id<b.id;
}
法一,结构体+自定义排序
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N =1e5+10;
struct Order
{
int t;
int id;
}order[N];
struct Shop
{
int rank;
int last;
bool queue;
}shop[N];
int n,m,t;
bool cmp(const Order&a,const Order&b) //自定义排序方式
{
if (a.t!=b.t) return a.t<b.t;
else return a.id<b.id;
}
int main()
{
scanf("%d%d%d",&n,&m,&t);
for (int i=0;i<m;i++)
{
int ts,id;
scanf("%d%d",&ts,&id);
order[i]={ts,id};
}
sort(order,order+m,cmp);
for (int i=0;i<m;i++)
{
int ts=order[i].t,id=order[i].id;
int cnt= ts==shop[id].last?0:ts-shop[id].last-1;
shop[id].rank=max(shop[id].rank-cnt,0);
if (shop[id].rank<=3) shop[id].queue=false;
shop[id].rank+=2;
if (shop[id].rank>5) shop[id].queue=true;
shop[id].last=ts;
}
for(int i = 1;i <= n;i++)
{
if(shop[i].last < t)
{
int cnt = t - shop[i].last;//减去t+1~last时段无订单时优先级减法计算
shop[i].rank = max(shop[i].rank - cnt,0);//结果比0小还是0
if(shop[i].rank<=3) shop[i].queue = 0;//维护优先缓存
}
}
int ans=0;
for(int i = 1;i <= n;i++)
{
if(shop[i].queue) ans++;//统计优先缓存中个数
}
printf("%d\n",ans);
return 0;
}
法二,y总的pair(pair默认按照第一关键字排序)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define x first
#define y second
const int N =1e5+10;
typedef pair<int,int>PII;
PII order[N];
bool priority[N];
int score[N],last[N];
int n,m,T;
int main()
{
scanf("%d%d%d",&n,&m,&T);
for (int i=0;i<m;i++)
scanf("%d%d",&order[i].x,&order[i].y);
sort(order,order+m);
for (int i=0;i<m;)
{
int j=i;
while (j<m&&order[i]==order[j])j++;
int t=order[i].x,id=order[i].y,cnt=j-i;
score[id]-=t-last[id]-1;
if (score[id]<0) score[id]=0;
if (score[id]<=3) priority[id]=false;
score[id]+=cnt*2;
if (score[id]>5) priority[id]=true;
i=j;
last[id]=t;
}
for (int i=1;i<=n;i++)
{
if (last[i]<T)
{
score[i]-=T-last[i];
if (score[i]<=3) priority[i]=false;
}
}
int ans=0;
for (int i=1;i<=n;i++)
{
if (priority[i]) ans++;
}
printf("%d\n",ans);
return 0;
}