最直接的题解(学完结构体的萌新都可以看)
2026-06-29 20:47:39
发布于:上海
38阅读
0回复
0点赞
因为楼主是个蒟蒻,不会难的手打,所以用的是比较直接的手法,包各位看懂
#include<bits/stdc++.h>//万能头~
using namespace std;
int n,k;
long long sum;
struct y{
int v,l;
}b[100010];//用结构体存储优惠卷,这里解释一下,v->value l->last,简写
bool cmp(y a,y b){
return a.l<b.l;//cmp排序按照优惠卷的持续时间排序
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int f,p;
long long t;
cin>>f>>p>>t;
sum+=p;//这里直接先全部加上,如果后面可以使用优惠卷,再单独加
if(f==0){
b[++k].v=p;//存储优惠卷,++k指的是先加再用
b[k].l=t+45;//优惠卷的持续时间
}else{
sort(b+1,b+k+1,cmp);//先排序,保证快过期的在前面
int k1=k;//用k1记录原有的k减去过期的和用掉的优惠卷的数量
for(int j=1;j<=k;j++){
if(b[j].l<t){//优惠卷过期
b[j].v=0;
b[j].l=1000000055;//置大值,t最大10的9次方,l最大就是加上45,1000000045,这里多10,方便排序
k1--;//优惠卷过期
}else if(b[j].l!=0&&b[j].v>=p&&b[j].l>=t){
//这里第一个条件可以删掉,我最开始做时l置0了,不过排序会出错,第二个判断优惠卷可抵消的价格是否大于坐地铁的价格,第三个条件判断优惠卷持续时间是否大于t,这里应该可以删掉,当时做时脑子有点炸了
sum-=p;
b[j].v=0;
b[j].l=1000000055;
k1--;
j=k+1;//只需要用一张优惠卷,直接跳出循坏,其实用break就行了
}
}
sort(b+1,b+k+1,cmp);//再次排序,将过期优惠卷,用掉的优惠卷,排到后面,方面k变成k1
k=k1;
}
}
cout<<sum;//输出就大功告成啦!
return 0;
}
看到这给个免费的赞吧,本蒟蒻凹了半小时……
这里空空如也







有帮助,赞一个