难，

原题链接：1032.Trapped in the Haybales Bronze--Bronze

福中

2026-06-21 20:41:15

发布于：浙江

1阅读

0回复

0点赞

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Bale {
long long s;
long long p;
};

bool compareBales(const Bale& a, const Bale& b) {
return a.p < b.p;
}

int main() {
// 优化 IO
ios::sync_with_stdio(false);
cin.tie(NULL);

int n;
if (!(cin >> n)) return 0;

vector<Bale> bales(n);
for (int i = 0; i < n; ++i) {
    cin >> bales[i].s >> bales[i].p;
}

// 按位置排序
sort(bales.begin(), bales.end(), compareBales);

if (n < 2) {
    // 如果少于2个干草包，Bessie 总是可以逃脱（或者没有封闭区间）
    // 题目隐含 N>=1，但如果 N=1，只有一个包，两边都是无限远，总能逃脱。
    // 区间数量为 N-1。如果 N=1，区间数 0，面积 0。
    cout << 0 << endl;
    return 0;
}

int num_intervals = n - 1;
vector<bool> can_left(num_intervals, false);
vector<bool> can_right(num_intervals, false);

// 计算 can_right
// 区间 i 位于 bales[i] 和 bales[i+1] 之间
for (int i = num_intervals - 1; i >= 0; --i) {
    long long dist = bales[i+1].p - bales[i].p;
    long long right_bale_size = bales[i+1].s;
    
    if (right_bale_size < dist) {
        if (i == num_intervals - 1) {
            // 右边是最后一个干草包，突破即逃脱
            can_right[i] = true;
        } else {
            // 依赖下一个区间的向右逃脱能力
            can_right[i] = can_right[i+1];
        }
    } else {
        can_right[i] = false;
    }
}

// 计算 can_left
for (int i = 0; i < num_intervals; ++i) {
    long long dist = bales[i+1].p - bales[i].p;
    long long left_bale_size = bales[i].s;
    
    if (left_bale_size < dist) {
        if (i == 0) {
            // 左边是第一个干草包，突破即逃脱
            can_left[i] = true;
        } else {
            // 依赖前一个区间的向左逃脱能力
            can_left[i] = can_left[i-1];
        }
    } else {
        can_left[i] = false;
    }
}

long long total_area = 0;
for (int i = 0; i < num_intervals; ++i) {
    if (!can_left[i] && !can_right[i]) {
        total_area += (bales[i+1].p - bales[i].p);
    }
}

cout << total_area << endl;

return 0;

}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论