221
技術社區[雲棲]
WIKIOI-1059 汽車裝油
1059 汽車裝油
題目描述 Description
設在一環行公路上有N個汽車站，每一站存有若幹數量的汽油（其中有的站可能不存）。現在使一輛原來沒有油的汽車從某站依反時針方向沿公路行駛，車站編號為反時針；每到一站即把該站的汽油全部帶上（出發的站也如此）。試求從哪幾站出發可以使汽車從該站出發環行一周，不致在中途因缺油而停車。
輸入描述 Input Description
輸入：輸入文件第一行有一個N（站點數N<1000）， 第二行有N個數字m1 m2 …… mn，數字間用空格作分隔符（mi描述第I站的存油數，mi≤100）， 第三行有N個數字w1 w2 …… wn，數字間用空格作分隔符（wi描述第I站至第I+1站汽車耗油量，wn描述第n站至第1站的耗油量，wi≤100）。
輸出描述 Output Description
輸出：在一行中按站點編號由小到大輸出可出發站點編號(中間用一個空格分隔)。若不存在可出發站點，則輸出“No Result!”。
樣例輸入 Sample Input
5
2 3 4 5 3
3 2 1 5 4
樣例輸出 Sample Output
2 3
AC代碼：
#include<stdio.h>
#include<algorithm>
using namespace std;
int w[2000],v[2000];
int Fun(int x,int n,int sum,int num)
{
while(num<n)
{
sum+=w[x];
sum-=v[x];
if(sum<0)
break;
if(x+1==n)
{x=0;num++;}
else
{x++;num++;}
//printf("sum=%d num=%d\n",sum,num);
}
if(num==n)
return 1;
else
return 0;
}
int main()
{
int i,n,sum=0,aws[2000],k=0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&w[i]);
for(i=0;i<n;i++)
scanf("%d",&v[i]);
for(i=0;i<n;i++)
{
//printf("i==%d:\n",i);
if(Fun(i,n,0,0)==1)
aws[k++]=i+1;
}
sort(aws,aws+k);
if(k!=0)
{
printf("%d",aws[0]);
for(i=1;i<k;i++)
printf(" %d",aws[i]);
puts("");
}
else
printf("No Result!\n");
return 0;
}
最後更新：2017-04-03 12:55:52