【二分搜索】最小化第k大的值
POJ 2010
题目地址:http://poj.org/problem?id=2010
题目大意
奶牛大学招生,从$C$头奶牛中招收$N$头。它们分别得分$score_i$,需要资助学费$aid_i$。希望新生所需资助不超过$F$,同时得分的中位数最高。求此中位数。
思路
这题以前用优先队列做过(【优先队列】POJ 2010),现在刷到二分搜索系列,可以用二分搜索解决。
刚开始用C(x)
来表示x是否能作为中位数。但是在判定过程中还是用到最大堆(:qゝ∠)
效率低下,看了一下题解,发现要分四种情况。
于是可以这样二分:
- 将奶牛成绩从小到大排序存放
- 将奶牛补助从小到大排序存放
- 二分搜索mid左右两个区间,统计符合要求的左右区间数量。
AC代码
/*************************************************************************
> File Name: 2010_2.cpp
> Author: Netcan
> Blog: http://www.netcan666.com
> Mail: 1469709759@qq.com
> Created Time: 2015-12-27 日 19:48:05 CST
************************************************************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int N, C, F;
int Median;
struct Cows {
int score, aid, rank_by_score;
} cows_rank_by_score[100005], cows_rank_by_aid[100005];
bool by_score(const Cows &a, const Cows &b) {
return a.score < b.score;
}
bool by_aid(const Cows &a, const Cows &b) {
return a.aid < b.aid;
}
void solve() {
Median = N >> 1;
sort(cows_rank_by_score, cows_rank_by_score+C, by_score);
for(int i=0; i<C; ++i) cows_rank_by_score[i].rank_by_score = i;
memcpy(cows_rank_by_aid, cows_rank_by_score, sizeof(Cows)*C);
sort(cows_rank_by_aid, cows_rank_by_aid+C, by_aid);
// for (int i = 0; i < C; ++i)
// printf("score: %d aid: %d id:%d\n", cows_rank_by_score[i].score, cows_rank_by_score[i].aid, cows_rank_by_score[i].rank_by_score);
// printf("=====\n");
// for (int i = 0; i < C; ++i)
// printf("score: %d aid: %d\n", cows_rank_by_aid[i].score, cows_rank_by_aid[i].aid);
int ans;
int lb = 0, ub = C; // [lb, ub)
// printf("Median: %d\n", Median);
while(ub - lb > 1) {
int left = 0, right = 0;
int mid = (lb + ub) >> 1;
int fee = cows_rank_by_score[mid].aid;
// printf("lb:%d ub:%d\n", lb, ub);
for(int i=0; i<C;++i) { // 按费用大小从小到大枚举
if((left < Median) && (fee + cows_rank_by_aid[i].aid <= F) && cows_rank_by_aid[i].rank_by_score < mid) { // 左边
++left;
fee += cows_rank_by_aid[i].aid;
}
else if((right < Median) && (fee + cows_rank_by_aid[i].aid <= F) && cows_rank_by_aid[i].rank_by_score > mid) { // 右边
++right;
fee += cows_rank_by_aid[i].aid;
}
}
// printf("left:%d right:%d\n", left, right);
if(left < Median && right < Median) {
ans = -1;
break;
}
else if(left < Median) lb = mid;
else if(right < Median) ub = mid;
else {
ans = cows_rank_by_score[mid].score;
lb = mid;
}
}
printf("%d\n", ans);
}
int main() {
#ifdef Oj
freopen("2010_2.in", "r", stdin);
#endif
scanf("%d%d%d", &N, &C, &F);
for (int i = 0; i < C; ++i)
scanf("%d%d", &cows_rank_by_score[i].score, &cows_rank_by_score[i].aid);
solve();
return 0;
}
POJ 3662
题目地址:http://poj.org/problem?id=3662
题目大意
Farmer John想从电话公司修一些电缆连接到他农场。已知$N$个电线杆编号为$1, 2, \cdots N$,其中1号已经连接电话公司,N号为农场,有$P$对电线杆可连接。
现给出$P$对电线杆距离$A_i, B_I, L_i$表示$A_i$和$B_i$可连接,需要长度为$L_i$的电缆。
电话公司赞助FJ $K$条免费电缆,额外的支出为剩下所需电缆的最大长度。
求出最小费用。
思路
刚开始用dfs
加队列搜索,TLE
了。。看来这类问题不得不用二分了。
设C(x)
表示,连接1号到N号电缆中>x长度有多少个。用来判断x是否免费。当第一个不免费,即为所求。
这里怎么求出>x有多少个呢?脑洞有点大,用最短路Dijkstra
求,>x设边权为1否则为0,跑出来的最短路即为个数,再和K
判断。
AC代码
/*************************************************************************
> File Name: 3662_2.cpp
> Author: Netcan
> Blog: http://www.netcan666.com
> Mail: 1469709759@qq.com
> Created Time: 2015-12-28 一 10:31:46 CST
************************************************************************/
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int N, P, K;
struct edge { // 顶点属性
int to, length;
edge(int to, int length): to(to), length(length) {}
bool operator<(const edge &b) const {
return length > b.length;
}
};
vector<edge> G[1005];
int d[1005];
bool dijkstra_C(int s, int x) { // 求出长度>x的最少个数(>x边权为1,否则为0,求最短路),判断x是否免费,当二分判定出第一个不免费的x,就是所求的最小的最大x。
priority_queue<edge> que;
memset(d, 0x3f, sizeof(d));
d[s] = 0;
que.push(edge(s, 0));
while(!que.empty()) {
edge p = que.top(); que.pop();
int v = p.to;
if(d[v] < p.length) continue;
for(unsigned int i=0; i<G[v].size(); ++i) {
edge e = G[v][i];
int len = e.length > x;
if(d[e.to] > d[v] + len) {
d[e.to] = d[v] + len;
que.push(edge(e.to, d[e.to]));
}
}
}
return d[N] <= K;
}
void solve() {
dijkstra_C(1, 1);
if(d[N] == 0x3f3f3f3f) {
printf("-1\n");
return;
}
int lb = -1, ub = 1000000+5; // (lb, ub)
while(ub - lb > 1) {
int mid = (lb + ub) >> 1;
if(dijkstra_C(1, mid)) ub = mid; // (lb, ub]
else lb = mid;
}
printf("%d\n", ub);
}
int main() {
#ifdef Oj
freopen("3662.in", "r", stdin);
#endif
scanf("%d%d%d", &N, &P, &K);
int a, b, l;
for (int i = 0; i < P; ++i) {
scanf("%d%d%d", &a, &b, &l);
G[a].push_back(edge(b, l));
G[b].push_back(edge(a, l));
}
solve();
return 0;
}
- 本文标题:【二分搜索】最小化第k大的值
- 本文字数:1,137
- 本文作者:Netcan
- 发布时间:2015年12月27日 - 21时36分
- 最后更新:2016年09月24日 - 22时18分
- 原始链接:http://www.netcan666.com/2015/12/27/【二分搜索】最小化第k大的值/
- 版权声明:"署名-非商用-相同方式共享 3.0"转载请保留原文链接及作者。
- 打赏: