C1160 - 加油站
题目描述
在一个圆形赛道上，有 N 个加油站，这些加油站按顺时针方向从 1 编号到 N。在第 i 个加油站，有 pi 加仑的汽油可用。从第 i 个加油站到它的顺时针邻站需要 qi 加仑的汽油。
现在考虑一场比赛，其中汽车从某个加油站出发时油箱是空的。你的任务是判断汽车是否能从任意一个加油站出发并完成一圈比赛。如果可以完成，请找出能够完成比赛的最小编号加油站 i。
输入格式
输入的第一行包含一个整数 T，表示测试用例的数量。每个测试用例的第一行包含一个整数 N，表示加油站的数量。接下来的几行包含 2 ∗ N 个整数：前 N 个整数表示每个加油站 i 提供的汽油量 pi，接下来的 N 个整数表示从加油站 i 到顺时针下一个加油站所需的汽油量 qi。
输出格式
对于每个测试用例，输出格式为 “Case c:”，其中 c 是从 1 开始的测试用例编号。然后根据情况输出以下内容：
- 如果汽车无法完成一圈，则输出 “Not possible”。
- 如果可以完成一圈，则输出 “Possible from station X”，其中 X 是汽车可以完成一圈的第一个加油站编号。
约束条件：
- T < 25（测试用例数量小于 25）
- N < 100001（加油站数量小于 100001）
样例 #1
样例输入 #1
2
5
1 1 1 1 1
1 1 2 1 1
7
1 1 1 10 1 1 1
2 2 2 2 2 2 2
样例输出 #1
Case 1: Not possible
Case 2: Possible from station 4
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：C1160.in，输出文件名为：C1160.out