[COCI2022-2023#2] Tramvaji 题解

简要题意

告诉一些站点之间的距离，求两站距离最小的两个站

思路

对于某个站点，站台1到他前面的站的距离一定已经处理好了，所以可以用一个数组维护前缀和，从前面某个站转移过来，最后统计就行了

Code:

#include <bits/stdc++.h>
using namespace std;
namespace IO{inline long long read() {long long res = 0; bool f = 0;char ch = getchar();while (ch < '0' || ch > '9')f |= (ch == '-'), ch = getchar();while (ch >= '0' && ch <= '9')res = (res << 3) + (res << 1) + ch - '0', ch = getchar();return f ? -res : res;}
}
using IO::read;
const int MAXN = 1e3 + 5;
int dist[MAXN];
int n;
int main() {// freopen("tramvaji.in", "r", stdin);// freopen("tramvaji.out", "w", stdout);n = read();for (int i = 2; i <= n; ++i) {string s;int y, t;cin >> s;if (s == "Patrik") {t = read();dist[i] = t;}else if (s == "Josip") { y = read(), t = read();dist[i] = dist[y] + t;}}int min_time = 0x3f3f3f3f, s = 0;for (int i = 2; i <= n; ++i) {if (dist[i] - dist[i - 1] < min_time)min_time = dist[i] - dist[i - 1], s = i - 1;}// cerr << dist[3][4];cout << min_time << ' ' << s << ' ' << s + 1;return 0;
}