Moo University - Financial Aid

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

题意:给你c个点,每个点有两个属性,一个是成为成绩g,一个是资金f,又给你总资金F,然后让你从这c个点中选出n个,这n个点满足两点:1,n个点的资金和不大于总资金F,2:n个点成绩的中位数尽可能的大。
题解:这一题开始自己也没有什么思路,看了别人的思路发现那样的做法好巧妙啊。
思路:首先按照成绩给c个点进行排序,然后对于每个i,计算出在i之前选出n/2个点,然后在i之后选出n/2个点,然后枚举每个i,选出最大的成绩。对于i之前的,只要选出n/2个点且资金之和最小的点即可,如果连最小的资金之和都满足不了资金和不大于F,则其他情况都不会满足。另外:对于选出资金和最小的n/2个。可以用最大堆或者优先队列来实现,每次加入堆中,只保留当前最小的n/2即可!

Moo University - Financial Aid
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<queue>
 6 using namespace std;
 7 struct Node{
 8    long long g;
 9   long long f;
10 }node[100002];
11 int cmp(Node a,Node b){
12   return a.g<b.g;
13 }
14 long long n,c;
15 long long aa[100002],bb[100002];//分别记录在i之前选出n/2个点最小的资金和和之后的。
16 long long f;
17 int main(){
18   while(~scanf("%I64d%I64d%I64d",&n,&c,&f)){
19      long long sum=0;
20   for(int i=1;i<=c;i++)
21   scanf("%I64d%I64d",&node[i].g,&node[i].f);
22     sort(node+1,node+c+1,cmp);
23       priority_queue<long long>Q;int counts=0;
24         for(int i=1;i<c-n/2;i++){
25          sum+=node[i].f;
26          Q.push(node[i].f);
27          counts++;
28          if(i>=n/2){
29               if(counts>n/2){
30                long long tmp=Q.top();
31                 Q.pop();
32                 sum-=tmp;
33               }
34                aa[i+1]=sum;
35          }
36     }
37       sum=0;counts=0;int counts2=0;
38      priority_queue<long long>Q2;
39       for(int i=c;i>n/2+1;i--){
40          sum+=node[i].f;
41          Q2.push(node[i].f);
42            counts++;
43            counts2++;
44          if(counts>=n/2){
45             if(counts2>n/2){
46           long long tmp=Q2.top();
47              Q2.pop();
48             sum-=tmp;
49             }
50             bb[i-1]=sum;
51          }
52     }
53 long long anss=0;bool flag=false;
54     for(int i=c-n/2;i>n/2;i--){
55         if(bb[i]+aa[i]+node[i].f<=f){
56             flag=true;
57             anss=node[i].g;
58             break;
59         }
60     }
61     if(flag)printf("%I64d\n",anss);
62     else printf("-1\n");
63   }
64 
65 }
View Code

Moo University - Financial Aid

上一篇:【翻译】理解内存


下一篇:advanced dom scripting dynamic web design techniques Part One DOM SCRIPTING IN DETAIL CHAPTER 1 DO IT RIGHT WITH BEST PRACTICES