#UVa:10026-Shoemaker’s Problem

灆洢 2012-03-29 23:12:36

排序就可以得解,順序是以罰金與工作日期的比例大小來當基準。可以想成說,當我開始工作後就不用被罰這個罰金,所以可以當作賺了這個罰金,那當然我就要從每日能賺最多罰金的工作開始做才能使罰金最小了喔!

C++(0.008)

/*******************************************************/
/* UVa 10026 Shoemaker’s Problem                       */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/03/29                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

struct Work{
  int T;
  int S;
  int num;
};

bool cmp( Work a, Work b ){
  if( (double)a.S/(double)a.T > (double)b.S/(double)b.T ) return true;
  else if ( (double)a.S/(double)a.T == (double)b.S/(double)b.T )
    if( a.num < b.num ) return true;
  return false;
}

int main(){
  int testcase, N;
  Work shoemaker[1005];

  while( scanf( "%d", &testcase ) != EOF ){
    for( int i = 0 ; i < testcase ; i++ ){
      if( i ) printf( "\n" );
      scanf( "%d", &N );
      for( int j = 0 ; j < N ; j++ ){
        scanf( "%d%d", &(shoemaker[j].T), &(shoemaker[j].S) );
        shoemaker[j].num = j+1;
      }
      sort( shoemaker, shoemaker+N, cmp );

      for( int j = 0 ; j < N ; j++ ){
        if( j ) printf( " " );
        printf( "%d", shoemaker[j].num );
      }
      printf( "\n" );
    }
  }

  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料