4.2 二分、三分、01分数规划(题解）

这一块的问题大多都具有单调性，大部分有单调性的问题都能用二分来解决，主要的解题方法是二分 + 验证（计算，求和，01），但主要的难点在验证，需要多练习，多思考。

跳石头（noip2015）

题目描述：一年一度的“跳石头”比赛又要开始了！这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

整体思路：

一般看到求最小值最大或者求最大值最小都是用二分去解决，对于这道题先去枚举这个最小值，然后相差距离比这个最小值小的石头就是要移走的，计算他们的数量，若小于要移走的石头的数量说明取得值太小了，l变大即可。

代码实现细节：

对整个石头距离计算的时候可以在最后多算一块石头，这样的话最后一块石头的距离也可以被计算到。

代码实现：

#include<bits/stdc++.h>
using namespace std;
#define A 50050
const int inf =  1e9 + 3;
int L,M,N;
int a[A];
bool check(int x)
{
    int last = 0;
    int cnt = 0;
    for(int i = 1;i <= N + 1;i++)
    {
        if(a[i] - a[last] < x) cnt++;
        else last = i;
    }
    return cnt <= M;
}
int solved()
{
    int l = 0,r = inf;
    while(l + 1 < r)
    {
        int mid = (l + r) >> 1;
        if(check(mid)) l = mid;
        else r = mid;
    }
    return l;
}
int main()
{
    cin >> L >> N >> M;
    for(int i = 1;i <= N;i++)
    {
        cin >> a[i];
        //a[i] += a[i - 1];
    }
    a[N + 1] = L;
    cout << solved() << endl;
    return 0;
}

[USACO 2017 Dec P]Greedy Gift Takers

题目大意

有n头牛排队领礼物，但是牛牛不讲礼貌，第i头牛牛总是会从插在从队尾数第ai个牛的前面，问经过无限次的分发礼物，有多少头牛始终领不到礼物

解题思路：

经过观察可以知道，只要第i头牛拿不到礼物，第i头牛之后的所有牛都拿不到礼物，也就是说第i头牛前面的n - i头牛构成了死循环；假设我们去枚举构成死循环的区间长度，那要怎么样检验该区间是否构成死循环呢？假设这个区间的长度是len，如果当前这个区间里第i头牛的ai值大于(len + i)就说明这个循环是一个死循环，l就应该向后移动，问题就解决了。其实该区间内牛的排列顺序并不重要，因为只要有一头牛会导致区间变成死循环，那么该牛所在的区间一定是最后所求答案区间的一个子区间，并不会影响结果(因为验证如果为假那右指针就会左移，其实最后找到的是最小的死循环)。

CODE

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
int c[N],b[N];
int n;
bool comp(int a,int b)
{
    return a > b;
}
bool check(int mid)
{
    for(int i = 1;i <= mid;i++) b[i] = c[i];
    int limit = n - mid;
    sort(b + 1,b + 1 + mid);
    for(int i = 1;i <= mid;i++)
    {
        if(b[i] >= limit) return 0;
        limit++;
    }
    return 1;
}
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> c[i];
    int l = 0,r = n + 1;
    while(l + 1 < r)
    {
        int mid = (l + r) >> 1;                                           
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << n - l - 1 <<endl;
    return 0;
}

[CQOI2010]扑克牌

题目大意:

你有n种牌，第i种牌的数目为ci。另外有一种特殊的牌：joker，它的数目是m。你可以用每种牌各一张来组成一套牌，也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如，当n=3时，一共有4种合法的套牌：{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。给出n, m和ci，你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里（可以有牌不使用）

整体思路：

假设我有6张j，1张1，2张2，3张3.那我去枚举我能组成的套牌数量，假设是三套牌，那么我势必要拿2张j当1，一张j当2，此时joker够用，所以3套是可以组成的。但如果要组成四套牌，那么我要3张j当1，2张j当2，1张j当3，joker也够用但是我用了6张j，那就说明至少有一套牌中的j是重复的，此时肯定是不行的。所以：

计算的joker数不能多于我有的joker
计算的joker数不能多于我枚举的套牌数

k-th number

题目大意:

给定一个序列，给定一个k值，对于序列任意长度大于等于k的子区间，选取每个这样的区间中的第k大数组成一个新序列，求新序列的第M大数。

##整体思路：去枚举第M大的数字x，那么新序列里面肯定刚好有（M - 1）个比x大的数字，也就是说可以刚好找到（M - 1）个第k大数比x大的区间。若验证下来的数量比我枚举的x大说明x取小了。

代码实现细节：

寻找区间的时候可以使用双指针，左指针为L，右指针为R，如果L到R里面比x大的数已经刚好有K个了，那么R - n之间的序列都满足条件；
当条件和1相同时，若第L个数比x个小，其实忽略第L个数也不影响答案，所以L++就可以。 3.直到可以直接算的区间都算完了，那么L再往后移动，再去寻找下一个满足条件的区间知道右指针达到序列末尾为止。

OVER!!!