简单的贪心
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 5 const int MAXN = 110; 6 7 struct worker 8 { 9 char name[20]; 10 int A, B; 11 int cost; 12 }; 13 14 int N, M, L; 15 worker W[MAXN]; 16 17 int cmp( const void *a, const void *b ) 18 { 19 worker *c = ( worker* )a; 20 worker *d = ( worker* )b; 21 if ( c->cost != d->cost ) return c->cost - d->cost; 22 else return strcmp( c->name, d->name ); 23 } 24 25 void solve( int i ) 26 { 27 int a = N; 28 int sum = 0; 29 while ( a != M ) 30 { 31 // printf("a=%d\n", a); 32 if ( a / 2 >= M && ( a / 2 ) * W[i].A > W[i].B ) 33 { 34 a /= 2; 35 sum += W[i].B; 36 } 37 else 38 { 39 --a; 40 sum += W[i].A; 41 } 42 } 43 W[i].cost = sum; 44 return; 45 } 46 47 int main() 48 { 49 int T, tt = 0; 50 char temp[20]; 51 char ch; 52 scanf( "%d", &T ); 53 while ( T-- ) 54 { 55 scanf( "%d%d%d", &N, &M, &L ); 56 for ( int i = 0; i < L; i++ ) 57 { 58 getchar(); 59 int k = 0; 60 while( ch = getchar(), ch != ':' ) 61 temp[k++] = ch; 62 temp[k] = '\0'; 63 strcpy( W[i].name, temp ); 64 scanf( "%d, %d", &W[i].A, &W[i].B ); 65 solve(i); 66 } 67 68 qsort( W, L, sizeof(W[0]), cmp ); 69 70 printf( "Case %d\n", ++tt ); 71 for ( int i = 0; i < L; i++ ) 72 printf( "%s %d\n", W[i].name, W[i].cost ); 73 } 74 return 0; 75 }