题目

{% fold 点击显/隐题目 %}

You are given a list of train stations, say from the station $1$ to the station $100$. The passengers can order several tickets from one station to another before the train leaves the station one. We will issue one train from the station $1$ to the station $100$ after all reservations have been made. Write a program to determine the minimum number of seats required for all passengers so that all reservations are satisfied without any conflict. Note that one single seat can be used by several passengers as long as there are no conflicts between them. For example, a passenger from station $1$ to station $10$ can share a seat with another passenger from station $30$ to $60$.
Several sets of ticket reservations. The inputs are a list of integers. Within each set, the first integer (in a single line) represents the number of orders, $n$, which can be as large as $1000$. After $n$, there will be $n$ lines representing the $n$ reservations; each line contains three integers $s, t, k$, which means that the reservation needs $k$ seats from the station $s$ to the station $t$ .These ticket reservations occur repetitively in the input as the pattern described above. An integer $n = 0$ (zero) signifies the end of input.
For each set of ticket reservations appeared in the input, calculate the minimum number of seats required so that all reservations are satisfied without conflicts. Output a single star '*' to signify the end of outputs.
1 10 8 20 50 20 3 2 30 5 20 80 20 40 90 40 0
20 60
{% endfold %}

题解

对于一个有100个站点的火车，给你火车预定表(从s站到t站需要k个座位),询问你整列车最少需要多少座位

需要注意如果同一站有上有下,重复部分不需要额外的作为(先下后上)

数据量比较小,直接暴力搞就行,不用线段树维护

代码

{% fold 点击显/隐代码 %}```cpp Train Seats Reservation https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
#include
#include
using namespace std;

const int maxn = 105;

typedef long long ll;
ll seats[maxn];

void add(int s, int t, ll k) {
for (int i = s; i < t; ++i)
seats[i] += k;
}

ll get() {
ll Max = 0;
for (int i = 1; i <= 100; ++i)
Max = max(Max, seats[i]);
return Max;
}

int main() {
cin.tie(0);
cin.sync_with_stdio(false);
int n;
while (cin >> n, n != 0) {
memset(seats, 0, sizeof(seats));
while (n--) {
int s, t;
ll k;
cin >> s >> t >> k;
add(s, t, k);
}
cout << get() << endl;
}
cout << "*" << endl;
return 0;
}

{% endfold %}