珍珠（bead），珍珠bead

珍珠（bead），珍珠bead

題目描述

       有n顆形狀和大小都一致的珍珠，它們的重量都不相同。n為整數，所有的珍珠從1到n編號。你的任務是發現哪顆珍珠的重量剛好處於正中間，即在所有珍珠的重量中，該珍珠的重量列(n+1)/2位。下面給出將一對珍珠進行比較的辦法：
給你一架天平用來比較珍珠的重量，我們可以比出兩個珍珠哪個更重一些，在作出一系列的比較後，我們可以將某些肯定不具備中間重量的珍珠拿走。
　　例如，下列給出對5顆珍珠進行四次比較的情況：
　　1、珍珠2比珍珠1重
　　2、珍珠4比珍珠3重
　　3、珍珠5比珍珠1重
　　4、珍珠4比珍珠2重
　　根據以上結果，雖然我們不能精確地找出哪個珍珠具有中間重量，但我們可以肯定珍珠1和珍珠4不可能具有中間重量，因為珍珠2、4、5比珍珠1重，而珍珠1、2、3比珍珠4輕，所以我們可以移走這兩顆珍珠。
寫一個程序統計出共有多少顆珍珠肯定不會是中間重量。

輸入輸出格式

輸入描述：

輸入文件第一行包含兩個用空格隔開的整數N和M，其中1<=N<=99，且N為奇數，M表示對珍珠進行的比較次數，接下來的M行每行包含兩個用空格隔開的整數x和y，表示珍珠x比珍珠y重。

輸出描述：

輸出文件僅一行包含一個整數，表示不可能是中間重量的珍珠的總數。

輸入輸出樣例

輸入樣例#1：

5 4
2 1
4 3
5 1
4 2

輸出樣例#1：

2

思路

先輸入數據，然後按照比較情況把每個數的大小情況列出來，最後將不可能的珍珠的數量輸出。

代碼

#include<stdio.h> int a[100][100],b[3][100]={0}; int main() { int n,i,m,j,k=0,s; scanf("%d%d",&n,&m); for(i=1;i<=m;i++) for(j=1;j<=2;j++) scanf("%d",&a[i][j]); s=n/2+1; for(i=1;i<=m;i++) { b[a[i][1]][1]=a[i][1]; b[a[i][1]][3]++; b[a[i][2]][1]=a[i][2]; b[a[i][2]][2]++; } for(i=1;i<=m;i++) { b[a[i][1]][3]=b[a[i][1]][3]+b[a[i][2]][3]; b[a[i][2]][2]=b[a[i][2]][2]+b[a[i][1]][2]; } for(i=1;i<=n;i++) if(b[i][2]>=s||b[i][3]>=s) k++; printf("%d",k); return 0; } View Code