程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj1323-Game Prediction(貪心思想),gameprediction

poj1323-Game Prediction(貪心思想),gameprediction

編輯:C++入門知識

poj1323-Game Prediction(貪心思想),gameprediction


貪心的思想:盡量的從最大值找起。然後在剩余之中,再從最大值找起。
一,題意:
  M個人,每人N張牌,每輪比較誰出的牌大,最大者為勝。現在給定M和N,以及你的牌,要求輸出你至少能確保獲得幾輪的勝利
  從"至少能贏幾輪"可以看出:每個人必定都從最大的牌開始出。(只判定輸贏兩種情況即可)
二,思路:
  1,輸入並從小到大排序;
  2,循環並記錄贏的次數;
  3,輸出;
三,步驟:
  1,sort函數排序
  2,先最大的牌比較,再從剩余的牌中,找最大的牌比較,依次循環下去,直到手中牌出完。
    循環開始:i = n-1(手中最大的牌)循環條件win+lose != n(牌未出完)循環處理 i--(每次循環完手中的牌跳到前一張);
    if 手中最大的牌值等於牌中最大的牌值時,必贏win++ ; max--;
    else 必輸lose++ ; max -= 2;
   注意:贏了,牌中最大牌值減一,輸了減二。
  3,輸出。

1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int main(){ 5 int m , n , Case = 0 ; 6 int a[1005]; 7 while(cin>>m>>n,m||n){ 8 Case++; 9 for(int i = 0 ; i < n ; i++){ 10 cin>>a[i]; 11 } 12 sort(a,a+n); //從小到大排序 13 int win = 0 , lose = 0 ; 14 int max = n*m ; //存儲牌中最大的牌 15 for(int i = n - 1 ; win+lose != n ; i-- ){ //win+lose==n 表示手上的牌已經出完 16 if(max==a[i]){ 17 win++; //牌中最大的牌==手上最大的牌時,必贏一次 18 max--; //贏了,牌中最大的牌值只要減一即可 19 } 20 else{ //否則,必輸一次。 21 lose++; //記錄輸的次數 22 max-=2; //輸了,牌中最大的牌值減二 23 } 24 } 25 cout<<"Case "<<Case<<": "<<win<<endl; 26 } 27 return 0; 28 } View Code

版權聲明:本文為博主原創文章,未經博主允許不得轉載。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved