P5661 [CSP-J 2019] 公交換乘 - 洛谷 | 計算機科學教育新生態(tài) (luogu.com.cn)

思路如下：

用一個數(shù)組來存儲現(xiàn)有的優(yōu)惠劵，每次乘公交時遍歷數(shù)組，若有符合條件的立即調用

每張優(yōu)惠券只能用一次，還需要記錄每張票的使用狀況（用了/還沒用）

所以就定義一個結構體

struct cu{
long long tim;    //獲得優(yōu)惠券的時間
int pr;                //優(yōu)惠券的價格
};

還需要一個布爾數(shù)組記錄票是否被使用過

bool us[100010];

當然把這個值定已進結構體里也是可以的

代碼如下：

#include<bits/stdc++.h>
using namespace std;
struct cu{
long long tim;//獲得優(yōu)惠券的時間
int pr;//優(yōu)惠券的價格
};
cu c[100010];//優(yōu)惠券箱子
int po;
bool us[100010];//記錄優(yōu)惠券是否被使用過
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;//哨兵，記錄是否有可用的優(yōu)惠券
for(int i=1; i<po; i++)
{
if(us[i])continue;//票已經(jīng)被用過了
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;
}

測完發(fā)現(xiàn)只得40分，出現(xiàn)了TLE

當然可以開啟O2優(yōu)化AC

分析數(shù)據(jù)結構后發(fā)現(xiàn)：
極限數(shù)據(jù)1051，假設開始的時候全坐地鐵，坐了5?104 次以后，我們的盒子里面有好多票啊。后面全坐公交，要坐5?104 次，每次都在這個大盒子里面找合適的票，復雜度O(n2),總計算量2.5?109，我們在超時的邊緣瘋狂試探啊。

這時可以發(fā)現(xiàn)優(yōu)惠券獲得的時間是由早到晚的，換句話說就是編號為 i 的票超時了，那么所有編號<=i 的票就都超時了

故我們可以定義一個數(shù)據(jù)head，記錄最后一個超時的票，搜索時直接從head開始就好

AC代碼如下：

#include<bits/stdc++.h>
using namespace std;
struct cu{
long long tim;//獲得優(yōu)惠券的時間
int pr;//優(yōu)惠券的價格
};
cu c[100010];//優(yōu)惠券箱子
int po;
bool us[100010];//記錄優(yōu)惠券是否被使用過
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;//哨兵，記錄是否有可用的優(yōu)惠券
for(int i=head; i<po; i++)
{
if(us[i])continue;//票已經(jīng)被用過了
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;
}

代碼結束，草神附上