CSP-J 2019 公交换乘

P5661 [CSP-J 2019] 公交换乘 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路如下：

用一个数组来存储现有的优惠劵，每次乘公交时遍历数组，若有符合条件的立即调用

每张优惠券只能用一次，还需要记录每张票的使用状况（用了/还没用）

所以就定义一个结构体

struct cu{
long long tim;    //获得优惠券的时间
int pr;                //优惠券的价格
};

还需要一个布尔数组记录票是否被使用过

bool us[100010];

当然把这个值定已进结构体里也是可以的

代码如下：

#include<bits/stdc++.h>
using namespace std;
struct cu{
long long tim;//获得优惠券的时间
int pr;//优惠券的价格
};
cu c[100010];//优惠券箱子
int po;
bool us[100010];//记录优惠券是否被使用过
int n,ans;
int g,p,t;
int main()
{
// freopen("transfer.in","r",stdin);
// freopen("transfer.out","w",stdout);
cin>>n;
while(n>0)
{
cin>>g>>p>>t;
if(g==0)//坐地铁
{
ans+=p;
c[po].tim=t;
c[po].pr=p;
po++;
}
if(g==1)//坐公交
{
bool sh=true;//哨兵，记录是否有可用的优惠券
for(int i=1; i<po; i++)
{
if(us[i])continue;//票已经被用过了
if(t-c[i].tim>45)//票超时了
{
us[i]=true;
}
else if(c[i].pr>=p)//价格是否足够
{
us[i]=true;
sh=false;
break;
}
}
if(sh)ans+=p;//没有能用的劵只能掏钱了
}
n--;
}
cout<<ans;
return 0;
}

测完发现只得40分，出现了TLE

当然可以开启O2优化AC

分析数据结构后发现：
极限数据10⁵1，假设开始的时候全坐地铁，坐了5∗10⁴ 次以后，我们的盒子里面有好多票啊。后面全坐公交，要坐5∗10⁴ 次，每次都在这个大盒子里面找合适的票，复杂度O(n²),总计算量2.5∗10⁹，我们在超时的边缘疯狂试探啊。

这时可以发现优惠券获得的时间是由早到晚的，换句话说就是编号为 i 的票超时了，那么所有编号<=i 的票就都超时了

故我们可以定义一个数据head，记录最后一个超时的票，搜索时直接从head开始就好

AC代码如下：

#include<bits/stdc++.h>
using namespace std;
struct cu{
long long tim;//获得优惠券的时间
int pr;//优惠券的价格
};
cu c[100010];//优惠券箱子
int po;
bool us[100010];//记录优惠券是否被使用过
int n,ans;
int g,p,t;
int head; //记录最后一张超时的票
int main()
{
// freopen("transfer.in","r",stdin);
// freopen("transfer.out","w",stdout);
cin>>n;
while(n>0)
{
cin>>g>>p>>t;
if(g==0)//坐地铁
{
ans+=p;
c[po].tim=t;
c[po].pr=p;
po++;
}
if(g==1)//坐公交
{
bool sh=true;//哨兵，记录是否有可用的优惠券
for(int i=head; i<po; i++)
{
if(us[i])continue;//票已经被用过了
if(t-c[i].tim>45)//票超时了
{
us[i]=true;
head=i;//超时了赶紧记下来
}
else if(c[i].pr>=p)//价格是否足够
{
us[i]=true;
sh=false;
break;
}
}
if(sh)ans+=p;//没有能用的劵只能掏钱了
}
n--;
}
cout<<ans;
return 0;
}

代码结束，草神附上