可以证明若从A点到B点时走不动了，则从A到B的途中的那些点也都到达不了B。
假设A点后是C点，则A点到达C点时只有两种情况：有剩余的油量，或者没有剩余。这两种情况都比直接从C点出发只好不差。所以在更好的情况下无法到达B点，那么更坏的情况更无法到达B点。
那么可以进行剪枝，枚举一个点A作为起点，若该点在途中某一点B停止了，那么下一次直接从B点开始枚举。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
int T, n;
int has[maxn], need[maxn];
int check(int u) {
int sum = has[u];
for (int i = 0; i < n; i++) {
if (need[(u + i) % n] > sum)return u + i + 1;
sum -= need[(u + i) % n];
sum += has[(u + i + 1) % n];
}
return -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
for (int t = 1; t <= T; t++) {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> has[i];
}
for (int i = 0; i < n; i++) {
cin >> need[i];
}
cout << "Case " << t << ": ";
int now, re = 0;
int cnt;
bool flg = 0;
for (cnt = 0; cnt < n;) {
int v = check(cnt);
if (v == -1) {
cout << "Possible from station " << cnt + 1 << endl;
flg = 1;
break;
}
cnt = v;
}
if(!flg)
cout << "Not possible" << endl;
}
return 0;
}
|
