MYF

UVa 11093 Just Finish it up

Posted on | In | | Visitors

题目链接

UVa 11093

解题方法：贪心

题目分析

题目大意

    有n个加油站，按照顺时针形成一个闭合的环，提供每一个加油站i可加的油量ai，以及从加油站i到加油站i+1的耗油量bi，问：是否能从这n个站中的一个站出发，能走完这个圈，如果可以，输出起点，否则输出不行。

解析

    做这道题首先要搞清楚这么一个情况，假设环路上有i,j,k三个加油站，并且i<j<k(顺时针方向)。如果：有车从i出发(在i的时候，车本来是没有油的，但是加了a[i]的油，然后出发)，可以到达k-1，但是到达不了k。那么：该车从j出发，也到达不了k。从i出发能到达k-1，也就表示，从i出发能到达j，到j点时最坏的情况是油刚好耗尽，这就相当于从j出发了，否则，到j的时候油是有一定剩余的，仍然到不了k，那么不剩余的话，更到不了k了。

    明白了上面这个情况，就好做多了，输入的时候直接输入进去两个圈，放在一个数组里(转了一个圈之后直接往下一个下标扫就好了)。设置l、r，l作为起点，r作为终点，如果从l出发恰好到不了r，那么就直接把r设置为新的起点，一直这么扫，如果l在前n个下标(即转了一圈之内)都没有找到结果，那么必然impossible了。

    那么如何判断l到不了r呢？可以这样操作，从l出发，用一个变量(代码中的num)记录到某一站剩余的油量，每次到一站加一下a[i]-b[i]，如果num出现负数，即油不够了，那必然到不了这一站了。

其他

    本题采用的方法，是找到答案即停止。按照个人习惯，一般是设置一个标签label，一旦找到答案就goto label，这是实际上是不太好的，即使写起来方便。但是goto语句太老了(各种c语言入门书里都这么说)，另外会造成结构混乱、可读性差等缺点。所以这次也学习了一下别人的姿势，建立一个记录答案的变量，找到答案就停，利用if、break语句，让代码看起来更优美一些。

参考题解

    http://blog.csdn.net/u014569598/article/details/38870013

代码

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
49
50
51
52
53
54
55
56
57
58
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define PI acos(-1)
#define debug         pf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 100005<<1
int a[maxn],b[maxn];
int main(){
    int T,n,l,r,ans;
    scanf("%d",&T);
    for (int cas=1; cas<=T; cas++) {
        ans=-1;
        scanf("%d",&n);
        for (int i=0; i<n; i++) {
            scanf("%d",a+i);
            a[i+n]=a[i];
        }
        for (int i=0; i<n; i++) {
            scanf("%d",b+i);
            b[i+n]=b[i];
        }
        
        /*****核心代码*****/
        for (l=0; l<n; l=r) {
            int sum=0,num=0;
            r=l;
            while (ans==-1&&(num+=a[r]-b[r++])>=0) {
                if (++sum==n) {
                    ans=l;
                }
            }
            if (ans!=-1) {
                break;
            }
        }
        /*****核心代码*****/
        
        if (ans==-1) {
            printf("Case %d: Not possible\n",cas);
        }
        else
            printf("Case %d: Possible from station %d\n",cas,ans+1);//ans+1是因为l是从下标0~n-1
    }
}