題意大概說(shuō)下
N頭奶牛想上大學(xué)，每個(gè)奶牛有一個(gè)SAT分?jǐn)?shù)和一個(gè)助學(xué)金數(shù)目。奶牛大學(xué)只能提供M個(gè)名額以及K助學(xué)金數(shù)目。求一種分配方案使得奶牛大學(xué)錄取的牛中SAT分?jǐn)?shù)在中位數(shù)上的分?jǐn)?shù)最大。
思路:
可以對(duì)奶牛的分?jǐn)?shù)排序后二分確定中位數(shù)。開(kāi)兩個(gè)數(shù)組,datas,datac，前者按照奶牛分?jǐn)?shù)排序，后者按照奶牛助學(xué)金數(shù)目排序。二分枚舉中位數(shù)，然后進(jìn)行驗(yàn)證：
按照datac從低到高順序在總和小于等于k的情況下統(tǒng)計(jì)處落在左區(qū)間的數(shù)目left和右區(qū)間的數(shù)目right
如果left>m/2&&right>m/2，當(dāng)前方案可行，嘗試中位數(shù)更大的方案
如果left<m/2&&right<m/2，則不可能
如果left<m/2&&right>m/2，中點(diǎn)應(yīng)該向右移動(dòng)
如果left>m/2&&right<m/2，中點(diǎn)應(yīng)該向左移動(dòng)
注意考慮中點(diǎn)的覆蓋情況。
還有，可能調(diào)整到最后也沒(méi)法滿足條件，那么也輸出-1
具體看程序吧
1 # include <cstdio>
2 using namespace std;
3 # include <algorithm>
4 # include <cstring>
5 int n,c,f;
6 struct node
7 {
8 int s,c;
9 int id;
10 }cows[100005],cowc[100005];
11 int rank[100005];
12 bool cmps(node a,node b)
13 {
14 return a.s<b.s;
15 }
16 bool cmpc(node a,node b)
17 {
18 return a.c<b.c;
19 }
20 int chk(int pos)
21 {
22 int left=0,right=0,tf=f;
23 bool mid=false;
24 for(int i=0;i<c;i++)
25 if(rank[cowc[i].id]<pos&&left<n/2)
26 if(tf>=cowc[i].c)
27 left++,tf-=cowc[i].c;
28 else break;
29 else if(rank[cowc[i].id]==pos&&!mid)
30 if(tf>=cowc[i].c)
31 mid=true,tf-=cowc[i].c;
32 else break;
33 else if(rank[cowc[i].id]>pos&&right<n/2)
34 if(tf>=cowc[i].c)
35 right++,tf-=cowc[i].c;
36 else break;
37 if(left>=n/2&&right>=n/2&&mid) return 0;
38 else if(left>=n/2) return 1;
39 else if(right>=n/2) return -1;
40 else if(left<n/2&&right<n/2) return -2;
41 }
42 int main()
43 {
44 scanf("%d%d%d",&n,&c,&f);
45 for(int i=0;i<c;i++)
46 {
47 scanf("%d%d",&cows[i].s,&cows[i].c);
48 cows[i].id=i;
49 }
50 memcpy(cowc,cows,sizeof(cows));
51 sort(cows,cows+c,cmps);
52 sort(cowc,cowc+c,cmpc);
53 /* printf("sorted by s\n");
54 for(int i=0;i<c;i++)
55 printf("(%d,%d)\n",cows[i].id,cows[i].s);
56 printf("\n");
57 printf("sorted by c\n");
58 for(int i=0;i<c;i++)
59 printf("(%d,%d)\n",cowc[i].id,cowc[i].c);
60 printf("\n");*/
61 int s=n/2,e=c-1-n/2;
62 for(int i=0;i<c;i++)
63 rank[cows[i].id]=i;
64 while(s<=e)
65 {
66 int mid=(s+e)/2;
67 switch(chk(mid))
68 {
69 case -1:
70 s=mid+1;
71 break;
72 case 1:
73 e=mid-1;
74 break;
75 case 0:
76 s=mid+1;
77 break;
78 case -2:
79 printf("-1\n");
80 return 0;
81 };
82 }
83 if(chk(s-1)==0)
84 printf("%d\n",cows[s-1].s);
85 else
86 printf("-1\n");
87 // system("pause");
88 return 0;
89 }
90