1241.外卖优先级

引入：结构体排序

结构体排序的两种方式：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;
}