AcWing 1241. 外卖店优先级
原题链接
简单
作者:
落日飞车
,
2021-04-09 09:28:53
,
所有人可见
,
阅读 528
存储:
开辟两个结构体数组,分别用来代表商家和订单
商家结构体包括两次相邻的时刻和该商家的优先级,数组下标是商家编号
订单结构体包括订单时刻及订单的商家编号,数组下标不设置明确意义
思路:
1.现将订单按照传入时间排序(结构体排序)
2.依次考察每一个订单,找到对应商家,处理商家优先级
应该先减后加,即先减去time1和time2间隔中应该降低的优先级,再加
上接单的优先级,避免本应因优先级<=3掉出缓存区但因为先加上优先级2
而没有掉出的bug,(比如优先级为4时有两种可能:第一种是从2加上来,这
个2可能是从5以上数字掉下来的,也有可能是从0加上来的,但是这种情况商家
是不在缓存区的;第二种就是从5掉下来的,这种情况因为优先级仍大于3所以不
会出缓存区。如果先加后减,就有可能让第一种情况变为第二种,导致本应不在
缓存区的商家仍在缓存区))
AC代码:
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 1e5 + 10;
struct lulu
{
int time1 = 0;
int time2 = 0;
int lev;
}sal[N];//商家结构体数组
struct dudu
{
int t;
int id;
}putin[N];//订单结构体数组
bool cmp(struct dudu a, struct dudu b)
{
return a.t < b.t;
}//将订单按照时间先后排序
int ans[N];
int res = 0;
int main()
{
int n, m, T;
cin>>n>>m>>T;
for( int i = 1; i <= m; i++ )
cin>>putin[i].t>>putin[i].id;
sort(putin+1, putin + m+1, cmp);
for( int i = 1; i <= m; i++ )//处理每一个订单
{
sal[putin[i].id].time2 = putin[i].t;
if(sal[putin[i].id].time1 == 0 || sal[putin[i].id].time2 - sal[putin[i].id].time1 <= 1)
//如果接第一单或者在时间间隔一秒内接单 优先级不降低
goto end;
int chuchu;
chuchu = abs(sal[putin[i].id].time2 - sal[putin[i].id].time1 - 1);
if(sal[putin[i].id].lev > chuchu)
sal[putin[i].id].lev -= chuchu;
else
sal[putin[i].id].lev = 0;//优先级最低降为0
sal[putin[i].id].time1 = sal[putin[i].id].time2;
if(sal[putin[i].id].lev > 5)
ans[putin[i].id] = 1;
else if(sal[putin[i].id].lev <= 3)
ans[putin[i].id] = 0;
end:
{
sal[putin[i].id].lev += 2;
sal[putin[i].id].time1 = sal[putin[i].id].time2;
if(sal[putin[i].id].lev > 5)
ans[putin[i].id] = 1;
else if(sal[putin[i].id].lev <= 3)
ans[putin[i].id] = 0;
}
}
for( int i = 1; i <= n; i++ )
//遍历每一个商家
{
int tmp = T - sal[i].time1;
sal[i].lev -= tmp;
//有可能商家最后接单不是T,需要考虑减少的优先级
if(sal[i].lev <= 3)
ans[i] = 0;
if(ans[i] == 1)
res++;
}
cout<<res<<endl;
return 0;
}