sicily 1134. 积木分发

Description

歌手The Pancakes到幼儿园跟小朋友玩耍，她到达的时候小朋友们已经争着积木玩了。小朋友都想要更多的积木砌一个自己喜欢的图形，砌完就可以和The Pancakes合照。同时，The Pancakes手上还有一些积木，她可以把手上的这些积木全部给一个小朋友，然后等该小朋友砌完后就可以收回所发的积木和该小朋友原先手上的积木。但她不知道能否让所有的小朋友都和她合照，聪明的你可以帮助她吗？

Input
输入包含多个数据。

每个数据的第一行是两个正整数n和s，1≤n≤10000，1≤s≤1000000，表示一共有n位小朋友，The Pancakes手上有s块积木。以下有n行，每行有两个正整数，a和b，1≤a，b≤10^9，表示第i个小朋友手上有a块积木，还需要b块积木才能够砌完。

输入n=0时表示结束。

Output
如果可以让所有小朋友都和Pancake合照，就输出YES；否则，输出NO。

贪心，从小到大排好，依次发过去再收回来就行了，如果按顺序收过去有不行的，后面也肯定不行

这题不准用qsort（会RF），所以要自己写。当然因为时间限制有10s，冒泡或者选择排序也能过（3、4s左右），不过自己写个快排放上去只要0.1s

View Code

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 typedef struct
 4 {
 5     int have;
 6     int want;
 7 } Kid;
 8 
 9 Kid list[10010];
10 void quick( Kid a[], int l, int r );
11 
12 int main()
13 {
14     int n, s;
15     int i;
16     int flag;
17     
18     while( scanf("%d %d", &n, &s) && n != 0 )
19     {
20         for( i = 0; i < n; i++ )
21         {
22             scanf("%d %d", &list[i].have , &list[i].want ) ;
23         }
24         quick( list, 0, n-1 );
25         
26         flag = 1;
27         
28         for( i = 0; i < n; i++ )
29         {
30             if( s < list[i].want )
31             {
32                 flag = 0; 
33                 break;
34             }
35             s = s + list[i].have ;
36         }
37 
38         if( flag ) 
39             printf("YES\n");
40         else 
41             printf( "NO\n");
42     }
43     
44     return 0;
45 }
46 
47 void quick( Kid a[], int l, int r )
48 {
49     int i, j;
50     Kid x;
51     if ( l >= r )
52         return;
53     
54     i = l;
55     j = r;
56     x = a[i];
57     
58     while( i < j )
59     {
60         while ( i < j && a[j].want > x.want )
61             j--;
62         if ( i < j )
63             a[i++] = a[j];
64         
65         while ( i < j && a[i].want < x.want )
66             i++;
67         if ( i < j )
68             a[j--] = a[i];
69     }
70     
71     a[i] = x;
72     quick( a, l, i-1);
73     quick( a, i+1, r);
74     
75 }