hihoCoder#1838 : 鎕鎕鎕贪心

题解：

　　神奇的贪心题，，，感觉每次做贪心题都无从下手。。。

　　我们首先按照a对所有卡片从小到大排序，然后从1开始，从连续的两张牌中取b最大的，最后一张单出来的也取了。

　　可以证明，这样的方案一定是合法的。

　　为什么呢？

　　假设我们将排序后的牌按照(1, 2) (3, 4) ……这样的方式两两分组，那么既然我们每次都是取b最大的那张，b的限制显然我们已经满足了。

　　现在来考虑a，假设我们遇到了最坏的情况，在每一组里面，我们都取到了a最小的那个，即我们取到了第1, 3, 5,……张牌（因为已经排好序了，所以a最小的一定是这些），那么这个时候我们可以改变一下分组方式由原来的(1, 2) (3, 4) ……变成1, (2, 3), (4, 5) ……(2 * n, 2 * n + 1),那么你可以发现，这时我们取的牌就变成了任意组当中a最大的那张，因此a也是满足条件的。

　　证明完毕。

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 210000

 int n;

 struct card{

     int a, b, id;

 }s[AC];

 inline bool cmp(card x, card y)

 {

     return x.a < y.a;

 }

 inline int read()

 {

     int x = ;char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 void pre()

 {

     n = read();

     int b =  * n + ;

     for(R i = ; i <= b; i ++)

         s[i].a = read(), s[i].b = read(), s[i].id = i;

     sort(s + , s + b + , cmp);

 }

 void work()

 {

     int b =  * n;

     for(R i = ; i <= b; i += )

     {

         if(s[i].b > s[i + ].b) printf("%d\n", s[i].id);

         else printf("%d\n", s[i + ].id);

     }

     printf("%d\n", s[ * n + ].id);

 }

 int main()

 {

     freopen("in.in", "r", stdin);

     pre();

     work();

     fclose(stdin);

     return ;

 }

巴特西

hihoCoder#1838 : 鎕鎕鎕贪心

最新文章

热门文章

巴特西

hihoCoder#1838 : 鎕鎕鎕 贪心

最新文章

热门文章

hihoCoder#1838 : 鎕鎕鎕贪心