Divide and conquer:Moo University - Financial Aid(POJ 2010)

本文主要是介绍Divide and conquer:Moo University - Financial Aid(POJ 2010)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

　　　　　　　　　　　　　　　　　　Moo University - Financial Aid　

　　其实是老题了http://www.cnblogs.com/Philip-Tell-Truth/p/4926008.html

　　这一次我们换二分法来做这一道题，其实二分法比我以前那个方法好想一点，主要是这次我们可以根据下标进行二分，然后排两次序，第一次是根据分数来排序，然后记录分数的序，接下来就把aid排一次序，然后我们就可以进行二分了

　　参考http://www.hankcs.com/program/cpp/poj-2010-moo-university-financial-aid-binary-search.html

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <functional>
 4 
 5 using namespace std;
 6 
 7 struct _set
 8 {
 9     int score, aid, rank_score;
10 }Cows_Score[100001], Cows_Aid[100001];
11 bool rank_score(_set &a, _set &b)
12 {
13     return a.score < b.score;
14 }
15 bool aid_score(_set &a, _set &b)
16 {
17     return a.aid < b.aid;
18 }
19 
20 void solve(const int, const int, const int);
21 
22 int main(void)
23 {
24     int N, Cows_Sums, F;
25 
26     while (~scanf("%d%d%d", &N, &Cows_Sums, &F))
27     {
28         for (int i = 0; i < Cows_Sums; i++)
29             scanf("%d%d", &Cows_Score[i].score, &Cows_Score[i].aid);
30         sort(Cows_Score, Cows_Score + Cows_Sums, rank_score);
31         for (int i = 0; i < Cows_Sums; i++)
32             Cows_Score[i].rank_score = i;//给score的号排序，等一下二分的时候要用到
33         memcpy(Cows_Aid, Cows_Score, sizeof(_set)*Cows_Sums);
34         sort(Cows_Aid, Cows_Aid + Cows_Sums, aid_score);
35 
36         solve(N, Cows_Sums, F);
37     }
38     return 0;
39 }
40 
41 void solve(const int N, const int Cows_Sums, const int F)
42 {
43     int lb = 0, rb = Cows_Sums, mid,left, right, tmp_sum;
44     bool m, n;
45     while (rb - lb > 1)//注意这里是对下标进行二分，对于aid直接找就可以了，注意一些细节上的问题就好
46     {
47         mid = (lb + rb) / 2;
48         tmp_sum = Cows_Score[mid].aid;
49         left = 0; right = 0;
50         for (int i = 0; i < Cows_Sums; i++)
51         {
52             if ((Cows_Aid[i].rank_score < mid) && (tmp_sum + Cows_Aid[i].aid <= F) && left < N / 2)
53             {
54                 tmp_sum += Cows_Aid[i].aid;
55                 left++;
56             }
57             else if ((Cows_Aid[i].rank_score > mid) && (tmp_sum + Cows_Aid[i].aid <= F) && right < N / 2)
58             {
59                 tmp_sum += Cows_Aid[i].aid;
60                 right++;
61             }
62         }
63         m = left < N / 2 ? 0 : 1;
64         n = right < N / 2 ? 0 : 1;
65         if (!m&&!n)
66         {
67             printf("-1\n");
68             return;
69         }
70         else if (m == 0 || (m == 1 && n == 1))
71             lb = mid;
72         else if (n == 0)
73             rb = mid;
74 
75     }
76     printf("%d\n", Cows_Score[lb].score);
77 }