求解

cjj(不加团)

2024-09-14 21:01:29

发布于：广东

64阅读

0回复

0点赞

代码：

#include <bits/stdc++.h>
using namespace std;

int p, t;
bool cmp(pair<int, int> t1, pair<int, int> t2) {
    if (t1.first < p && t2.first < p)
        return t1.first > t2.first;
    if (t2.first < p) return 1;
    if (t1.first < p) return 0;
    if (abs(t2.second - t) > 45) return 1;
    if (abs(t1.second - t) > 45) return 0;
    return t1.second < t2.second;
}

int main() {
    int n, sum = 0;
    cin >> n;
    vector<pair<int, int>> a;
    for (int i = 1; i <= n; i ++) {
        for (auto [x, y] : a)
            cout << x << " " << y << " ";
        cout << endl;
        bool h;
        cin >> h >> p >> t;
        if (!h) {
            sum += p;
            a.push_back({p, t});
            continue;
        }
        if (a.empty()) {
            sum += p;
            continue;
        }
        sort(a.begin(), a.end(), cmp);
        if (a.front().first < p || abs(a.front().second - t) > 45)
            sum += p;
        else {
            int tt = a.front().second;
            a.pop_back();
        }
    }
    cout << sum;

    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 3

消失的AC 无尽的RE

这个比较函数想实现"优先消耗获得最早的优惠票"，但逻辑写错了。

6天前来自浙江
2
消失的AC 无尽的RE

当你找到合适的优惠票后，应该移除那张票，但你是pop_back()，这移除的是最后一张票，而不是你排序后找到的那张。

6天前来自浙江
2

消失的AC 无尽的RE

我喜欢用其他方法来做

#include <bits/stdc++.h>
using namespace std;

struct Ticket {
int price; // 地铁票价
int time; // 获得时间
bool used; // 是否已使用
};

int main() {
int n;
cin >> n;

long long total = 0;
deque<Ticket> tickets;  // 存储优惠票

for (int i = 0; i < n; i++) {
    int type, price, time;
    cin >> type >> price >> time;
    
    if (type == 0) {  // 地铁
        total += price;
        tickets.push_back({price, time, false});
    } else {  // 公交车
        // 清理过期票（超过45分钟）
        while (!tickets.empty() && time - tickets.front().time > 45) {
            tickets.pop_front();
        }
        
        // 寻找可用优惠票
        bool found = false;
        for (auto it = tickets.begin(); it != tickets.end(); it++) {
            if (!it->used && it->price >= price) {
                // 找到可用票
                it->used = true;
                found = true;
                break;
            }
        }
        
        if (!found) {
            total += price;
        }
    }
    
    // 定期清理已使用的票，避免队列过长
    // 注意：不能直接清理未过期的票，因为它们可能后面还有用
}

cout << total << endl;
return 0;

}

6天前来自浙江