What is the best way to feed a pet with candy?

本文共计1111个文字，预计阅读时间需要5分钟。

A. Candy Time Limit: 100 msMemory Limit: 100 MBInput: Output: The hero of the game Cut the Rope is a little monster named Om Nom. He loves candies. And what a coincidence! He also is the hero of today's problem. Given n candies, where n is an integer, your task is to find the maximum number of candies Om Nom can eat in one go.

A. Feed with Candy

time limit per test

memory limit per test

input

output

The hero of the Cut the Rope game is a little monster named Om Nom. He loves candies. And what a coincidence! He also is the hero of today's problem.

ncandies of two types (fruit drops and caramel drops), thei-th candy hangs at the height ofhicentimeters above the floor of the house, its mass ismi. Om Nom wants to eat as many candies as possible. At the beginning Om Nom can make at mostxcentimeter high jumps. When Om Nom eats a candy of massy, he gets stronger and the height of his jump increases byy

What maximum number of candies can Om Nom eat if he never eats two candies of the same type in a row (Om Nom finds it too boring)?

Input

nandx(1 ≤ n, x ≤ 2000)

nlines contains three integersti, hi, mi(0 ≤ ti ≤ 1;1 ≤ hi, mi— the type, height and the mass of thei-th candy. If numberti

Output

Print a single integer — the maximum number of candies Om Nom can eat.

Sample test(s)

input

5 3 0 2 4 1 3 1 0 8 3 0 20 10 1 5 5

output

4

原本代码交上了 谁知道被一外国小伙Hack了。没办法誰让自己的代码没有人家的更完美啊，经过修改AC的代码终于写出来了。代码如下：

#include<stdio.h> #include<string.h> #include<stdlib.h> struct node { int a,bp,c,d; }x[2010]; int cmp (const void *a,const void *b) { struct node * aa = (struct node *)a; struct node * bb = (struct node *)b; return bb->c - aa->c; } int main() { int n,m,i,j; while(scanf("%d%d",&n,&m)!=EOF) { int count1 = 0,count2 = 0,h = 1; for(i=0;i<2010;i++) { x[i].d = 0; } for(i=0;i<n;i++) { scanf("%d%d%d",&x[i].a,&x[i].bp,&x[i].c); } qsort(x,n,sizeof(x[0]),cmp); int pp = 1; int tt = m; while(h == 1) { for(i=0;i<n;i++) { if(tt>=x[i].bp && pp!=x[i].a && x[i].d == 0) { tt = tt + x[i].c; x[i].d = 1; pp = x[i].a; count1++; break; } } if(i == n) { h == 0; break; } } h == 1; pp = 0; for(i=0;i<2010;i++) { x[i].d = 0; } while(h == 1) { for(i=0;i<n;i++) { if(m>=x[i].bp && pp!=x[i].a && x[i].d == 0) { m = m + x[i].c; x[i].d = 1; pp = x[i].a; count2++; break; } } if(i == n) { h = 0; break; } } if(count1>count2) { printf("%d\n",count1); } else { printf("%d\n",count2); } } return 0; } 下面是被Hack的代码： #include<stdio.h> #include<string.h> #include<stdlib.h> struct node { int a,bp,c,d; }x[2010]; int cmp (const void *a,const void *b) { struct node * aa = (struct node *)a; struct node * bb = (struct node *)b; return bb->c - aa->c; } int main() { int n,m,i,j; while(scanf("%d%d",&n,&m)!=EOF) { int count = 0,h = 1; for(i=0;i<2010;i++) { x[i].d = 0; } for(i=0;i<n;i++) { scanf("%d%d%d",&x[i].a,&x[i].bp,&x[i].c); } qsort(x,n,sizeof(x[0]),cmp); int k = 0; int pp = 11; while(h == 1) { k++; if(k == 1) { for(i=0;i<n;i++) { if(m>=x[i].bp) { m = m + x[i].c; x[i].d = 1; pp = x[i].a; count++; break; } } } else { for(i=0;i<n;i++) { if(m>=x[i].bp && pp!=x[i].a && x[i].d == 0) { m = m + x[i].c; x[i].d = 1; pp = x[i].a; count++; break; } } if(i == n) { h = 0; break; } } } printf("%d\n",count); } return 0; }

Note

4candies is to eat them in the order:1,5,3,2. Let's assume the following scenario:

1. 3. He can reach candies1and2. Let's assume that he eats candy1. As the mass of this candy equals4, the height of his jump will rise to3 + 4 = 7.
2. 2and5. Let's assume that he eats candy5. Then the height of his jump will be7 + 5 = 12.
3. 2and3. He won't eat candy2as its type matches the type of the previously eaten candy. Om Nom eats candy3, the height of his jump is12 + 3 = 15.
4. 2, the height of his jump is15 + 1 = 16. He cannot reach candy4.