A50005.公交换乘暴力解法

skirmish

2025-07-03 20:58:14

发布于：河南

59阅读

0回复

0点赞

这道题数据非常水可以直接暴力(~~我这是纯暴力足足用了600ms~~)，用一个数组存优惠票的时间，用一个数组存优惠票的价格。

#include <bits/stdc++.h>
using namespace std;
int t[100005],m[100005];//时间和价格
void del(int x[],int a){
    for (int i=a;i<=100000;i++){
        x[i]=x[i+1];
        if (x[i+1]==0) break;
    }
}
int main(){
    int n,a,b,c,ans=0,cnt=1;
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a>>b>>c;
        if (!a){//地铁
            t[cnt]=c;//时间
            m[cnt]=b;//价格
            cnt++;//优惠票的数量
            ans+=b;
        }
        else{公交
            bool flag=false;
            for (int j=1;j<=cnt;j++){
                if (c-t[j]<=45&&b<=m[j]){//优惠票可用
                    del(t,j);//删除优惠票
                    del(m,j);//同上
                    flag=true;
                    break;
                }
            }
            if (!flag) ans+=b;//优惠票不可用
        }
    }
    cout<<ans;
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

Srobot

我暴力的结果是 14个TLE ……

2025-08-20 来自广东

Srobot

回复Srobot

#include <iostream>
#include <algorithm>
using namespace std;
int now;
int pre;
struct inf{
    int price=0;
    int time;
}k[100010];
bool cbused(inf a){
    if(pre>a.price)
        return false;
    if(now-a.time>45)
        return false;
    return true;
}
bool cmp(inf a,inf b){
    if((cbused(a)&&cbused(b))||((!cbused(a))&&(!cbused(b))))
        return a.time<b.time;
    return cbused(a)>cbused(b);
}
int main(){
    int n;
    cin>>n;
    int sum=0;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        if(x==0){
            cin>>k[i].price>>k[i].time;
            sum+=k[i].price;
        }
        else{
            cin>>pre>>now;
            sort(k,k+n,cmp);
            if(cbused(k[0]))
                k[0].price=0;
            else
                sum+=pre;
        }
    }
    cout<<sum;
    return 0;
}

2025-08-20 来自广东