UVA-11903 Just Finish it up

题目大意：一个环形跑道上有n个加油站，每个加油站可加a[i]加仑油，走到下一站需要w[i]加仑油，初始油箱为空，问能否绕跑道一圈，起点任选，若有多个起点，找出编号最小的。

题目分析：如果从1号加油站开始走，若跑不完一圈，意味着到了某个站p的最大油量走不到下一站，则以2~p为起点都不能跑完一圈。

代码如下：

# include<iostream>

# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

int a[100005],w[100005],vis[100005];

int judge(int n)

{

    int s=0,k=0,t=0;

    vis[0]=1;

    for(int i=0;i<n;i=(i+1+n)%n){

        if(k==n) return s;

        t+=a[i];

        if(t<w[i]){

            s=(i+1+n)%n;

            if(vis[s]) return -1;

            vis[s]=1;

            k=t=0;

        }else{

            ++k;

            t-=w[i];

        }

    }

    return -1;

}

int main()

{

    int n,T,cas=0;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        for(int i=0;i<n;++i){

            scanf("%d",a+i);

            vis[i]=0;

        }

        for(int i=0;i<n;++i)

            scanf("%d",w+i);

        printf("Case %d: ",++cas);

        int k=judge(n);

        if(k==-1)

            printf("Not possible\n");

        else

            printf("Possible from station %d\n",k+1);

    }

    return 0;

}

巴特西

UVA-11903 Just Finish it up

最新文章

热门文章