ACM模版

描述

题解

和蓝桥杯上一道题目相似度达 99% ，贪心搞搞即可~~~

这个题放在六级着实有些夸张了，蓝桥杯才把他放在算法训练中，连算法提高都不算……所以，这个题本身也就二三级题的难度吧！

代码

#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int N, T;
ll D[MAXN], P[MAXN];

int main(int argc, const char * argv[])
{
//    freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    cin >> N >> T;
    for (int i = 0; i < N; i++)
    {
        cin >> D[i + 1] >> P[i];
        D[i + 1] += D[i];
    }
    P[N] = INF;

    ll cost = 0, state = 0;
    int max_len = T, pos = 0;
    for (int i = 1; i <= N; i++)
    {
        if (P[i] < P[pos] && (D[i] - D[pos]) <= max_len)
        {
            cost += ((D[i] - D[pos]) - state) * P[pos];
            pos = i;
            state = 0;
        }
        else if (P[i] >= P[pos] && (D[i] - D[pos]) <= max_len)
        {
            int tag = -1;
            double p = P[pos];
            for (int j = pos + 1; j <= N && (D[j] - D[pos]) <= max_len; j++)
            {
                if (P[j] < p)
                {
                    tag = j;
                    break;
                }
            }
            if (tag == -1 && (D[N] - D[pos]) <= max_len)
            {
                cost += ((D[N] - D[pos]) - state) * P[pos];
                pos = N;
                i = N;
                state = 0;
            }
            if (tag != -1)
            {
                cost += ((D[tag] - D[pos]) - state) * P[pos];
                pos = tag;
                i = tag;
                state = 0;
            }
            else
            {
                int tag = -1;
                double p = INF + 10;
                for (int j = pos + 1; j <= N && (D[j] - D[pos]) <= max_len; j++)
                {
                    if (P[j] < p)
                    {
                        tag = j;
                        p = P[j];
                    }
                }
                if (tag != -1)
                {
                    cost += (T - state) * P[pos];
                    state = T - (D[tag] - D[pos]);
                    pos = tag;
                    i = tag;
                }
            }
        }
    }

    if (pos == N)
    {
        cout << cost << '\n';
    }
    else
    {
        cout << "-1\n";
    }

    return 0;
}

参考

《蓝桥 ALGO 15 旅行家的预算》