本文共 3749 字,大约阅读时间需要 12 分钟。
题目可能排版有问题,导致出现一些乱码,具体请参考洛谷原题
著名旅游城市 B 市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交车的优惠方案:
现在你得到了小轩最近的公共交通出行记录,你能帮他算算他的花费吗?
输入文件的第一行包含一个正整数 nn,代表乘车记录的数量。
接下来的 nn 行,每行包含 3 个整数,相邻两数之间以一个空格分隔。第 ii 行的第 1 个整数代表第 ii 条记录乘坐的交通工具,0 代表地铁,1 代表公交车;第 2 个整数代表第 ii 条记录乘车的票价 price_ipricei ;第三个整数代表第 ii 条记录开始乘车的时间 t_iti(距 0 时刻的分钟数)。
我们保证出行记录是按照开始乘车的时间顺序给出的,且不会有两次乘车记录出现在同一分钟。
输出文件有一行,包含一个正整数,代表小轩出行的总花费。
60 10 31 5 460 12 501 3 960 5 1101 6 135
36
60 5 10 20 160 7 231 18 311 4 381 7 68
32
【输入输出样例 1 说明】
第一条记录,在第 3 分钟花费 10 元乘坐地铁。
第二条记录,在第 46 分钟乘坐公交车,可以使用第一条记录中乘坐地铁获得的优惠票,因此没有花费。
第三条记录,在第 50 分种花费 12 元乘坐地铁。
第四条记录,在第 96 分钟乘坐公交车,由于距离第三条记录中乘坐地铁已超过 45 分钟,所以优惠票已失效,花费 3 元乘坐公交车。
第五条记录,在第 110 分钟花费 5 元乘坐地铁。
第六条记录,在第 135 分钟乘坐公交车,由于此时手中只有第五条记录中乘坐地铁获得的优惠票有效,而本次公交车的票价为 6 元,高于第五条记录中地铁的票价 5 元,所以不能使用优惠票,花费 6 元乘坐公交车。
总共花费 36 元。
【输入输出样例 2 说明】
第一条记录,在第 1 分钟花费 5 元乘坐地铁。
第二条记录,在第 16 分钟花费 20 元乘坐地铁。
第三条记录,在第 23 分钟花费 7 元乘坐地铁。
第四条记录,在第 31 分钟乘坐公交车,此时只有第二条记录中乘坐的地铁票价高于本次公交车票价,所以使用第二条记录中乘坐地铁获得的优惠票。
第五条记录,在第 38 分钟乘坐公交车,此时第一条和第三条记录中乘坐地铁获得的优惠票都可以使用,使用获得最早的优惠票,即第一条记录中乘坐地铁获得的优惠票。
第六条记录,在第 68 分钟乘坐公交车,使用第三条记录中乘坐地铁获得的优惠票。
总共花费 32 元。
【数据规模与约定】
对于 30\%30% 的数据,n \leq 1000n≤1000,t_i \leq 10^6ti≤106。
另有 15\%15% 的数据,t_i \leq 10^7ti≤107,price_ipricei 都相等。
另有 15\%15% 的数据,t_i \leq 10^9ti≤109,price_ipricei 都相等。
对于 100\%100% 的数据,n \leq 10^5n≤105,t_i \leq 10^9ti≤109,1 \leq price_i \leq 10001≤pricei≤1000。
关于考试
本蒟蒻恨在ZJ,只能考个J组 QWQ
考试的时候一个break忘打了,调了半天,吓死laozi了
T1是真的水,比去年还要水(尽管我去年复赛都没进QWQ)
T2还好吧,结构体队列比较容易想到
T3。。一眼看还以为是DP,调了半天出不来,只好放弃,骗了10分QWQ(才知道是完全背包)
T4蒟蒻根本没想到奇偶数最短路,写暴搜骗了40
总体和去年差不多,感觉第四题比较好骗分
ZJ CSP-J 250,还不能保证文件问题。。。
自闭中QWQ
言归正传
T2我觉得比较容易想到结构体+队列,看到别的dalao开两个结构体,本蒟蒻参不透啊!我就开了一个。写法和楼上有点类似,又有点不一样。
****大致思路是,每次读入,先去掉过期地铁票。若乘地铁,直接付钱,信息入队。若乘公交车,扫一遍队列,找到符合要求的第一张票,并整理队列;若没有优惠,付钱吧。
贴上代码:
#includeusing namespace std;struct node{ int a,pr,t;//a交通工具,pr即price价格,t时间 }szh[100005];//结构体 node q[100005];//结构体队列,比较方便 int n,head,tail,ans;//队头队尾 ,队首是q[head+1],队尾是q[tail] ,非常关键 int main(){ //freopen("transfer.in","r",stdin); //freopen("transfer.out","w",stdout);//刚考完,文件不知道有没有打错,心慌慌。。。。 scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&szh[i].a,&szh[i].pr,&szh[i].t); while(head 45,出队,否则退出 ,注意不是<= if(szh[i].t-q[head+1].t>45) head++; else break;//考试的时候break没加,无限循环,运行错误,慌得一比 ,查了半小时。。。 } if(szh[i].a==0){ //乘地铁,入队,价格计入答案 ans+=szh[i].pr; q[++tail]=szh[i]; } else{ //公交车,分类讨论 if(head==tail){ //如果队列为空,则价格计入答案 ans+=szh[i].pr; } else{ //队列不为空,扫描一遍 int p=head;// head在扫描过程中不能变,所以定义一个指针 int f=0;//flag标记 while(p =szh[i].pr){ //如果找到队列中地铁票价高于当前公交车票价,停止扫描,免费 for(int j=p+1;j>=head+2;j--)//j的范围需要仔细思考,模拟 q[j]=q[j-1];//p+1之前的都前进一个单位 f=1;//标记,表示已扫到符合要求 head++;//队列长度-1 break;//退出循环 } else{ p++;//再往前扫 continue;//进入下一次循环(现在才发现是废话) } } if(f==0) ans+=szh[i].pr;// 如果没有符合要求的地铁票,乖乖掏出钱包 } } } printf("%d",ans);//Van美 return 0;}
本蒟蒻不会算复杂度,望大佬告知
PS:那个大样例好像出问题了,题目里给的10^5,大样例居然有10^6,还没有换行(同学说是格式问题),就炸了
后记:
2019.11.17:成为本蒟蒻在洛谷第一篇通过的
2019.11.18:发现了一些文件问题,文件夹多嵌套一个,导致250直接爆零,当场吐血
转载地址:http://hfuki.baihongyu.com/