Massive Algorithms: POJO 2010 -- Moo University

POJO 2010 -- Moo University - Financial Aid

http://poj.org/problem?id=2010

Description

Bessie noted that although humans have many universities they can attend, cows have none. To remedy this problem, she and her fellow cows formed a new university called The University of Wisconsin-Farmside,"Moo U" for short.

Not wishing to admit dumber-than-average cows, the founders created an incredibly precise admission exam called the Cow Scholastic Aptitude Test (CSAT) that yields scores in the range 1..2,000,000,000.

Moo U is very expensive to attend; not all calves can afford it.In fact, most calves need some sort of financial aid (0 <= aid <=100,000). The government does not provide scholarships to calves,so all the money must come from the university's limited fund (whose total money is F, 0 <= F <= 2,000,000,000).

Worse still, Moo U only has classrooms for an odd number N (1 <= N <= 19,999) of the C (N <= C <= 100,000) calves who have applied.Bessie wants to admit exactly N calves in order to maximize educational opportunity. She still wants the median CSAT score of the admitted calves to be as high as possible.

Recall that the median of a set of integers whose size is odd is the middle value when they are sorted. For example, the median of the set {3, 8, 9, 7, 5} is 7, as there are exactly two values above 7 and exactly two values below it.

Given the score and required financial aid for each calf that applies, the total number of calves to accept, and the total amount of money Bessie has for financial aid, determine the maximum median score Bessie can obtain by carefully admitting an optimal set of calves.

Input

* Line 1: Three space-separated integers N, C, and F

* Lines 2..C+1: Two space-separated integers per line. The first is the calf's CSAT score; the second integer is the required amount of financial aid the calf needs

Output

* Line 1: A single integer, the maximum median score that Bessie can achieve. If there is insufficient money to admit N calves,output -1.

Sample Input

Sample Output

http://www.hankcs.com/program/cpp/poj-2010-moo-university-financial-aid.html
奶牛大学：奶大招生，从C头奶牛中招收N头。它们分别得分score_i，需要资助学费aid_i。希望新生所需资助不超过F，同时得分中位数最高。求此中位数。

题意：奶牛学校招生，要录取n（奇数）个学生，报名了c个学生，每个学生有成绩s_i和需要的补助金f_i。学校的补助金一共为F元，挑选n个学生，f_1+f_2+f_i+....+f_n不得大于n，且n个奶牛的s_i的中位数最大，输出这个数？

https://www.cnblogs.com/ibilllee/p/9221758.html

最朴素的办法：按分数从小到大排列，枚举原点，从右到左扫，区间为[(m+1)/2,n-(m+1)/2]，计算左边最小和和右边最小和，判断是否是满足条件，满足即输出。

显然这种n²的办法是不行的。

我们要减复杂度，就要在枚举原点的同时维护左右两边最小和，如何维护？

优先队列+枚举，分治解法：

将奶牛按照成绩s_i从小到大排序，从 n/2 到 m-1-n/2枚举中位数，记录每个i的前面n/2数的f之和，和后面n/2数的f之后，然后枚举满足条件最大的中位数。

https://blog.csdn.net/liuke19950717/article/details/51057360
在保证中位数最大的情况下，如何保证正好取N个！
DP的话数据量太大，搜索也搜不动，贪心很难保证恰好取N个。

根据 sorce递增排序，枚举中位数a[i]！那么肯定在 [1,i-1]区间内取N/2个数，在 [i+1,C]内取N/2个数！

问题就转化为：求分别求区间 [1,i-1]、[i+1,C]中N/2个数的最小值。 N/2+1<=i<=C-N/2
这时需要一个高效的数据结构！
我们来维护一个大小为 N/2的最大堆。
例如对于区间 [1,i-1], 初始堆为 [1,N/2]， sum= sum([1,N/2].aid) （aid为所需资助）
每次拓展区间长度时，我们只需比较新扩展的结点(key)与堆顶元素(fro)的大小。 if (key<fro) 则弹出堆顶元素，并且使 key入堆，并更新 sum。（保证和最小！）
区间[i+1,C]也是一样。
最后倒序枚举中位数即可。

最大堆
2.4 加工并储存数据的数据结构
优先队列
先将奶牛排序，考虑每个奶牛作为中位数时，比它分数低（前面的）的那群牛的学费总和lower_i，后面的总和upper_i。然后从分数高往分数低扫描，满足aid_i + lower_i + upper_i <= F的第一个解就是最优解。
相比于这种“枚举”，还有一种利用二分搜索的快速实现：http://www.hankcs.com/program/cpp/poj-2010-moo-university-financial-aid-binary-search.html。

#define MAX_COW 100000 + 16

int N, C, F;

pair<int, int> cow[MAX_COW];

// 牛i作为中位数时，lower[i]表示分数低于它的牛的学费总和

int lower[MAX_COW], upper[MAX_COW];

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

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

    freopen("out.txt", "w", stdout);

#endif

    cin >> N >> C >> F;

    int half = N / 2;

    for (int i = 0; i < C; ++i)

{

        cin >> cow[i].first >> cow[i].second;   // 分数 <-> 学费

}

    sort(cow, cow + C);

{

        int total = 0;

        priority_queue<int> q;

        for (int i = 0; i < C; ++i)

{

            lower[i] = q.size() == half ? total : 0x3f3f3f3f;

            q.push(cow[i].second);

            total += cow[i].second;

            if (q.size() > half)

{

                // 然后踢掉一个学费最高的家伙

                total -= q.top(); q.pop();

}

}

}

{

        int total = 0;

        priority_queue<int> q;

        for (int i = C - 1; i >= 0; --i)

{

            upper[i] = q.size() == half ? total : 0x3f3f3f3f;

            q.push(cow[i].second);

            total += cow[i].second;

            if (q.size() > half)

{

                // 然后踢掉一个学费最高的家伙

                total -= q.top(); q.pop();

}

}

}

    int result;

    for (int i = C - 1; i >= 0; --i)

{

        if (lower[i] + cow[i].second + upper[i] <= F)

{

            result = cow[i].first;

            break;

}

}

    cout << result << endl;

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

struct node
{
int num,val;
}x[maxn];
int cmp(node a,node b)
{
if(a.num==b.num)
{
return a.val<b.val;
}
return a.num<b.num;
}
int lower[maxn],upper[maxn];
int slove(int n,int m,int s)
{
memset(lower,-1,sizeof(lower));
memset(upper,-1,sizeof(upper));
sort(x,x+n,cmp);
int mid=m/2,cnta=0,cntb=0;
priority_queue<int> qa;
priority_queue<int> qb;
for(int i=0;i<n;++i)
{
lower[i]=(qa.size()==mid)?cnta:inf;
upper[n-i-1]=(qb.size()==mid)?cntb:inf;
qa.push(x[i].val);
qb.push(x[n-i-1].val);
cnta+=x[i].val;
cntb+=x[n-i-1].val;
if(qa.size()>mid)
{
cnta-=qa.top();
qa.pop();
}
if(qb.size()>mid)
{
cntb-=qb.top();
qb.pop();
}
}
for(int i=n-1;i>=0;--i)
{
if(lower[i]+x[i].val<=s-upper[i])
{
return x[i].num;
}
}
return -1;
}

X. Bisection
http://www.hankcs.com/program/cpp/poj-2010-moo-university-financial-aid-binary-search.html
现在用二分再做一遍。在分别排序分数和学费之后，以分数为界限将牛分为左右两个区间，统计左区间符合条件的数目left和右区间的数目right。讨论left 和right是否满足条件。以此为基础二分，实际上下面的谓词逻辑可以优化，但是目前看起来比较好懂。

分别用分数和所需补助金给奶牛排序，用分数为界限将奶牛分为左右两区间两部分，再分别查找左区间满足条件的奶牛数 left 和右区间满足条件的奶牛数 right。讨论 left 和 right 的值分情况取讨论如何修改下一次要查找的值。


int N, C, F;
int lower[MAX_COW], upper[MAX_COW];
struct Cow
{
 int rank_by_score, score, aid;
};
Cow cow_score[MAX_COW], cow_aid[MAX_COW];
bool less_by_score(Cow& a, Cow& b)
{
 return a.score < b.score;
}
bool less_by_aid(Cow& a, Cow& b)
{
 return a.aid < b.aid;
}
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
 freopen("in.txt", "r", stdin);
 freopen("out.txt", "w", stdout);
#endif
 ios::sync_with_stdio(false);
 cin.tie(0);
 cin >> N >> C >> F;
 int half = N / 2;
 for (int i = 0; i < C; ++i)
 {
  cin >> cow_score[i].score >> cow_score[i].aid;   // 分数  学费
 }
 sort(cow_score, cow_score + C, less_by_score);
 for (int i = 0; i < C; ++i)
 {
  cow_score[i].rank_by_score = i;
 }
 memcpy(cow_aid, cow_score, sizeof(Cow) * C);
 sort(cow_aid, cow_aid + C, less_by_aid);
 
 int lb = 0, ub = C, ans = -1;
 while (ub - lb > 1)
 {
  int mid = (ub + lb) >> 1;
  // 将牛分为左右两个区间，统计左区间符合条件的数目left和右区间的数目right
  // 情况比较多，总体是二分，实际上有四种情况
  int left = 0, right = 0, total_aid = cow_score[mid].aid;
  for (int i = 0; i < C; ++i)
  {
   if ((cow_aid[i].rank_by_score < mid) && (total_aid + cow_aid[i].aid <= F) && (left < N / 2))
   {
    total_aid += cow_aid[i].aid;
    ++left;
   }
   else if ((cow_aid[i].rank_by_score > mid) && (total_aid + cow_aid[i].aid <= F) && (right < N / 2))
   {
    total_aid += cow_aid[i].aid;
    ++right;
   }
  }
  // 四种情况
  if ((left < N / 2) && (right < N / 2))
  {
   ans = -1;
   break;
  }
  else if (left < N / 2)
  {
   lb = mid;
  }
  else if (right < N / 2)
  {
   ub = mid;
  }
  else
  {
   ans = cow_score[mid].score;
   lb = mid;
  }
 }
 cout << ans << endl;

Read full article from 2010 -- Moo University - Financial Aid

POJO 2010 -- Moo University - Financial Aid

Labels

Popular Posts