P5661

AnnaQ · 2023-07-29 15:35:09 · 个人记录

思路

输入完之后先判断一下他是否是坐的地铁或者是第一个，二者只要满足一个ans①就得加上这次的票钱，如果都不满足，那么，接进入第二个判断条件，如果满足的话，就开始循环注意，不要直接从零开始，要不然会TLE，而是得先比较一下大小，如果0更大，就从零开始，否则，就从i - 45开始，循环内部的判断条件缺一不可，第一个条件是判断第j次出行是否是乘坐的地铁，第二个条件是判断该过没过有效期，第三个判断条件是看超没超那次的票钱，第四个条件是判断这张优惠券有没有被用过，如果都满足，那么，就将f设为1，并且跳出循环，后面这个if是判断能不能用优惠券的，如果不能，ans就加上这次的票钱，否则就不加，最后，把ans输出了就行了。

①：ans如果设在主函数内部了，一定要初始化为0！！！

AC Code

#include<bits/stdc++.h>
using namespace std;
struct traffic
{
    int l,p,c;
    long long t;
} a[100010];
long long n,ans,f;
int main()
{
    cin >> n;
    for(int i = 0;i < n;i++)
    {
        scanf("%d %d %lld",&a[i].l,&a[i].p,&a[i].t);
        if(i == 0 || a[i].l == 0)
        {
            ans += a[i].p;
        }
        else
        {
            if(a[i].t - a[i - 1].t <= 45)
            {
                for(int j = max(0,i - 45);j < i;j++)
                {
                    if(a[j].l == 0 && a[i].t - a[j].t <= 45 && a[i].p <= a[j].p && a[j].c == 0)
                    {
                        f = 1;  
                        a[j].c = 1;
                        break;
                    }
                }
            }
            if(!f)
            {
                ans += a[i].p;
            }
            f = 0;
        }
    }
    printf("%lld",ans);
    return 0;
}