首页 > ACM题库 > 九度OJ > 九度-1416-猴子吃坚果[解题代码]
2013
12-13

九度-1416-猴子吃坚果[解题代码]

题目描述:

动物园的猴子吃坚果的顺序都是按强壮程度来定的,最强壮的吃完才能轮到下一个,现在我们给出各个猴子的名字,强壮程度,吃饱的量,然后查询对应的猴子必须要扔多少坚果才可以轮到。

输入:

输入有多组,对于每组输入:

输入的第一行包括两个整数n(1<=n<=10000),代表动物园中猴子的个数,以及m(1<=m<=10000),代表我们要查询的次数。

        接下来的n行,每行包括一个字符串(代表猴子的名字,长度1<=len<=100),一个整数a(1<=a<=10000),代表猴子的强壮程度,一个整数b(1<=b<=10000),代表猴子吃饱所需要的食物量。

输出:

         对于每次查询,输出最少需要多少食物,被查询的这只猴子才能吃到食物。

样例输入:
3 2
monkey_a 4 2
monkey_b 3 4
monkey_c 5 3
monkey_a
monkey_c
4 2
monkey_a 4 2
monkey_b 3 4
monkey_c 5 3
monkey_d 5 3
monkey_a
monkey_c

样例输出:
4
1
7
1
提示:

 如果有两只猴子的强壮程度相同,就按照猴子名字的字母序来决定吃食物的先后顺序。


cpp 代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct M{
	char name[200];
	int pow;
	int cap;
}M,* pM;
int compareTo(const void *a,const void *b){
	if(((pM)a)->pow > ((pM)b)->pow){
		return -1;
	}else if(((pM)a)->pow == ((pM)b)->pow)
		return strcmp(((pM)a)->name,((pM)b)->name);
	else
		return 1;

}

int main(){
	int n,m;
	M monkey[10000];
	while(scanf("%d",&n) != EOF){
		scanf("%d",&m);
		for(int i=0; i<n; i++){
			scanf("%s",monkey[i].name);
			scanf("%d",&monkey[i].pow);
			scanf("%d",&monkey[i].cap);
		}
		qsort(monkey,n,sizeof(M),compareTo);
		for (int i = 0; i < m; i++) {

			char temp[200];
			scanf("%s",temp);
			long x = 1;
			for (int j = 0; j < n; j++) {
				if(strcmp(temp,monkey[j].name) == 0) {
					printf("%ld\n",x);
					break;
				} else
					x += monkey[j].cap;
			}
		}

	}
	return 0;
}



/**************************************************************
	Problem: 1416
	User: coder
	Language: C++
	Result: Accepted
	Time:60 ms
	Memory:2984 kb
****************************************************************/