两道二分，怎么还是二分。。。

快过年了，这几天总是想咕咕咕，但是还好我忍住了，但是CSAPP还是咕咕咕了嘤嘤嘤嘤嘤嘤嘤嘤嘤

今天的题应该只有两道二分有的说了吧，可能是学得太早了，对二分印象已经没有那么深了，最近做的题也没有用到二分的知识，加上之前对二分理解不够，导致现在还是不会用二分解题。。。

还好最近给的题有不少二分，总算可以弥补一下短板。。。。

HDU-4190 Distributing Ballot Boxes

这个题在做的时候确实是想到了二分，但是完全不知道该对什么二分，上网查过后才了解到这道题应该二分答案。。。。

算了，我不狡辩了，，，我之前真的不知道什么是二分答案。。。。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+5;
int a[N];
int n,b;
bool check(int x)
{
    int num=0;
    for(int i=1;i<=n;i++)
    {
        num+=a[i]/x;
        if(a[i]%x!=0)num++;
    }
    if(num>b)return true;
    else return false;
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>b)
    {
        if(n==-1&&b==-1)break;
        int maxx=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            maxx=max(maxx,a[i]);
        }
        int l=1;
        int r=maxx,mid;
        int t=1000;
        while(t--){
            mid=l+((r-l)>>1);
            if(check(mid)){
                l=mid;
            }
            else r=mid;
        }
        cout<<r<<endl;
    }
}

Codeforces 847B Preparing for Merge Sort

这道题其实就只有一个地方比较难以发现，每次放入的元素，要找从上到下队列尾第一个小于它的插入。所以，插入后，这个元素插入的队列的上面的队列尾元素都比这个元素大，因为每次插入的队列尾都小于当前元素，所以下面的队尾也比这个元素小

虽然我也不知道我在说什么总之，队列尾元素从上到下是递减的。。。

所以就能二分了嘛

因为要比队尾元素，从队首输出，或者比队首元素，从队尾输出，所以要用到双端队列

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+5;
int a[N];
deque<int> q[N];
int find(int len,int x)
{
    int l=1,r=len,mid;
    int t=400;
    while(t--){
        mid=l+((r-l)>>1);
        if(q[mid].back()>x){
            l=mid;
        }
        else{
            r=mid;
        }
    }
    return r;
}
int main()
{
    int n;
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int len=1;
    q[len].push_back(a[1]);
    for(int i=2;i<=n;i++)
    {
        int p=find(len,a[i]);
        if(q[len].back()>a[i]){
            len++;
            q[len].push_back(a[i]);
        }
        else q[p].push_back(a[i]);
    }
    for(int i=1;i<=len;i++)
    {
        cout<<q[i].front();
        q[i].pop_front();
        while(!q[i].empty())
        {
            cout<<' '<<q[i].front();
            q[i].pop_front();
        }
        cout<<endl;
    }
}