博客入口在这

想在此处看的就接着看吧。

这是一道水题

虽然说有点水，但是细节很多。感觉跟***差不多

细节：

1.优惠券生效的时间

优惠券生效的时间是45分钟，所以要记得加等号，不加难AC。

2.优惠券使用的顺序

优惠券是从早到晚使用，所以循环要从小到大走。

3.优惠券的生效对价钱的要求

优惠券是从地铁获得，如果要生效，必须使用在比这趟地铁的价格便宜的公交车费上。

4.优惠券的使用与否

如果只满足上述三点，也很难AC。如果不判断，还是会0分的。所以此处做个记忆化，记录哪些用了。因为这道题的数据范围很小，所以可以使用基数排序的方法来记录。

这些细节注意完后，代码大致如下：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int Maxn = 1e5;
struct Recode
{
    int By;//交通方式 
    int Prize;//价格 
    int Time;//时间点
}Re[Maxn];
int DaBiao[Maxn]; 
int main()
{
    int n;
    long long ans = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {

        scanf("%d %d %d", &Re[i].By, &Re[i].Prize, &Re[i].Time); 
        if(Re[i].By)//如果是公交车而且没被用过 
        {
            bool HP_SRC = false;
            for(int j = 1; j < i; j++)//寻找优惠券 
            {
                if(DaBiao[j])
                    continue; 
                else if(!Re[j].By && abs(Re[i].Time - Re[j].Time) <= 45 && Re[i].Prize <= Re[j].Prize)//如果有优惠券 
                {
                    HP_SRC = 1;
                    DaBiao[j] = 1;
                    break;
                }
            }
            if(!HP_SRC)
                ans += Re[i].Prize;
        }
        else
            ans += Re[i].Prize;

    }
    printf("%lld", ans);

    return 0;
}

当你将这个代码交上去时，会这样

也就是TLE几个点。吸过氧了，几乎什么都没有改变

这也就是我做这道题多用了1个多小时的细节。

我们可以看一下刚才那个代码的一个循环：for(int j = 1; j < i; j++)

如果认真读题的人当然没有我就会发现：从开始的话到了后面和大起来的时候就会很浪费时间，导致TLE。

所以我们就可以参考队列，因为队列是一个( ，先进先出)，符合题意。由于我们不取队头元素，所以我们只定义head（队尾我也不知道我怎么想的），然后去找有效的元素（时间差在45min内的）。改完的代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int Maxn = 1e5;
struct Recode
{
    int By;//交通方式 
    int Prize;//价格 
    int Time;//时间点
}Re[Maxn];
int DaBiao[Maxn];
int head = 1;
int main()
{
    int n;
    long long ans = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {

        scanf("%d %d %d", &Re[i].By, &Re[i].Prize, &Re[i].Time); 
        if(Re[i].By)//如果是公交车而且没被用过 
        {
            bool HP_SRC = false;
            for(int j = head; j < i; j++)//寻找优惠券 
            {
                if(Re[i].Time- Re[j].Time > 45)
                    head = j;
                if(DaBiao[j])
                    continue; 
                else if(!Re[j].By && abs(Re[i].Time - Re[j].Time) <= 45 && Re[i].Prize <= Re[j].Prize)//如果有优惠券 
                {
                    HP_SRC = 1;
                    DaBiao[j] = 1;
                    break;
                }
            }
            if(!HP_SRC)
                ans += Re[i].Prize;
        }
        else
            ans += Re[i].Prize;

    }
    printf("%lld\n", ans);

    return 0;
}

当然，你们不用去交，结果在此
。AC了。

总结：

这道题虽然看起来水，但是细节很多。