【二分搜索】最小化第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;
}