試題 演算法提高 盾神與積木游戲
問題描述
最近的m天盾神都去幼兒園陪小朋友們玩去了~
每個小朋友都拿到了一些積木，他們各自需要不同數量的積木來拼一些他們想要的東西，但是有的小朋友拿得多，有的小朋友拿得少，有些小朋友需要拿到其他小朋友的積木才能完成他的大作，如果某個小朋友完成了他的作品，那么他就會把自己的作品推倒，而無私地把他的所有積木都奉獻出來；但是，如果他還沒有完成自己的作品，他是不會把積木讓出去的喲~
盾神看到這么和諧的小朋友們感到非常開心，于是想幫助他們所有人都完成他們各自的作品，盾神現在在想，這個理想有沒有可能實作呢？于是把這個問題交給了他最信賴的你，
輸入格式
第一行為一個數m，
接下來有m組資料，每一組的第一行為n，表示這天有n個小朋友，接下來的n行每行兩個數，分別表示他現在擁有的積木數和他一共需要的積木數，
輸出格式
輸出m行，如果第i天能順利完成所有作品，輸出YES，否則輸出NO，
樣例輸入
2
2
2 2
1 3
3
1 5
3 3
0 4
樣例輸出
YES
NO
資料規模和約定
1<=n<=10000，1<=m<=10，
分析
我的思路方法和其他人比起來可能會有點復雜，首先定義一個二維陣列用來存放小孩現在的積木數和需要的積木數，然后類似一個冒泡排序，用需要的積木數-已有的積木數將差值最小的放在前面（如果不這樣，利用的積木將不完全），然后定義一個變數記錄可挪用的積木數，每當一個人可以完成時便加上這個人的積木數，我這里判斷能不能完成用的不是旗幟法，也可以用，最后根據是否可以輸出yes或者no，
二、使用步驟
代碼如下（示例）：
#include<stdio.h>
int main()
{
int i,j,z,x,m,n;
int a[10000][2];
int b[10],v=0;
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d",&n);
int zong=0,sum=0;
for(j=0;j<n;j++)
{
for(z=0;z<2;z++)
{
scanf("%d",&a[j][z]);
}
}
for(z=0;z<n;z++)
{
for(x=0;x<n-z-1;x++)
{
if(a[x][1]-a[x][0]>a[x+1][1]-a[x+1][0])//n
{
int c=a[x][1];
int d=a[x][0];
a[x][1]=a[x+1][1];
a[x][0]=a[x+1][0];
a[x+1][1]=c;
a[x+1][0]=d;
}
}
}
for(j=0;j<n;j++)
{
if(a[j][0]+zong>=a[j][1])
{
sum++;
zong+=a[j][0];
}
}
if(sum==n)
{
b[v]=1;
v++;
}
else
{
b[v]=0;
v++;
}
}
for(i=0;i<v;i++)
{
if(b[i]==1)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259817.html
標籤：其他
上一篇：STM32f4日記8之四輪三路尋跡小車實驗(小車實驗二：紅外模塊檢測尋跡(左拐，右拐，前進，停止))
下一篇：資料結構優化DP