分析
根据1.时间,2.店号 对订单进行排序
每次找出同一时间、同一店号的订单数量,集中进行处理:
- 求当前订单优先级:$a[id]=max(0,a[id]-(t-last[id]-1))$;
- 若当前订单优先级小于等于3,则离开缓冲区:$if(a[id]<=3) st[id]=0$;
- 当前订单优先级加上所有订单带来的热度:$a[id]+=cnt*2$;
- 若当前订单优先级大于5,则加入缓冲区:$if(a[id] > 5) st[id]=1$;
- 更新该店号上次有订单的时间:$last[i]=t$
循环上次操作,直到所有订单都被遍历。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;;
struct node{
int t,id;
bool operator<(const node &p) const{ //排序函数
if(t==p.t) return id<p.id;
return t<p.t;
}
}lst[N];
int n, m, T;
int a[N],last[N],ans;
unordered_map<int,int> st;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>T;
for(int i=0;i<m;i++) cin>>lst[i].t>>lst[i].id;
sort(lst,lst+m); //对订单进行排序
for(int i=0;i<m;)
{
int j=i;
while (j<m && lst[j].t==lst[i].t && lst[j].id==lst[i].id) j++; //将相同的订单取出来
int t=lst[i].t,id=lst[i].id,cnt=j-i; //t为当前时间,id为当前时间,cnt为相同订单数量
i=j;
a[id]=max(0,a[id]-(t-last[id]-1));
if(a[id]<=3) st[id]=0;
a[id]+=cnt*2;
if(a[id] > 5) st[id]=1;
last[id]=t;
}
for(int i=1;i<=n;i++)
if (last[i]<T) //若T时刻该店没有订单,则要减去其上次有订单时间到T的距离。
{
a[i]=max(0,a[i]-(T-last[i]));
if(a[i]<=3) st[i]=0;
}
for (int i=1;i<=n;i++) ans+=st[i];
cout<<ans;
return 0;
}
为什么last[id]=t 而不是last[id]=j-1 ?
请问下在 查找i订单后面相同的订单时,cnt=j-i不应该加一吗,因为如果i后面没有相同订单cnt不就为0了吗,那最后a[id]+=cnt不就等于没有加数吗
假如下标为1的订单是独一无二的,j从1开始遍历,到下标2就跳出循环,那么cnt=j-i=2-1=1,符合预期。
我学傻了,脑子一下子没有清醒,谢谢啦
nb