0x04 二分

最佳牛围栏

农夫约翰的农场由 块田地组成，每块地里都有一定数量的牛，其数量不会少于 头，也不会超过 头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 块地，其中 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入格式
第一行输入整数 和 ，数据间用空格隔开。
接下来 行，每行输入一个整数，第 行输入的整数代表第 片区域内包含的牛的数目。

输出格式
输出一个整数，表示平均值的最大值乘以 再 向下取整 之后得到的结果。

数据范围

输入样例：

10 6
6 
4
2
10
3
8
5
9
4
1

输出样例：

6500

二分平均值，然后check是否存在一个长度大于等于 k 的区间，平均值大于枚举值。
check方法：先让每个元素减去枚举的值之后，只需判断是否存在某个区间和大于 0 即可，利用前缀和优化。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 100010;
int n, k, a[N];
ll b[N];
bool check(ll x){
    for(int i=1;i<=n;i++){
        b[i] = a[i] - x + b[i-1];
    }
    ll mi = 0;
    for(int i=k;i<=n;i++){
        if(b[i] - mi >= 0)return true;
        mi = min(mi, b[i-k+1]);
    }
    return false;
}
int main(){
  scanf("%d%d", &n, &k);
  rep(i,1,n) {
    scanf("%d", &a[i]); a[i] *= 1000;
  }
  int l = 1000, r = 2000000;
  while(l < r) {
    int mid = (l + r + 1) >> 1;
    if(check(mid)) l = mid;
    else r = mid - 1;
  }
  printf("%d\n", l);
  return 0;
}

特殊排序

有 个元素，编号 ，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。
注意：不存在两个元素大小相等的情况。
也就是说，元素的大小关系是 个点与 %7D%7B2%7D#card=math&code=%5Cfrac%7BN%20%5Ctimes%20%28N-1%29%7D%7B2%7D&id=Q8Iex) 条有向边构成的任意有向图。
然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过 次提问来获取信息，每次提问只能了解某两个元素之间的关系。
现在请你把这 个元素排成一行，使得每个元素都小于右边与它相邻的元素。
你可以通过我们预设的 bool 函数 compare 来获得两个元素之间的大小关系。
例如，编号为 和 的两个元素，如果元素 小于元素 ，则 compare(a,b) 返回 true，否则返回 false。
将 个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。

数据范围

输入样例

[[0, 1, 0], [0, 0, 0], [1, 1, 0]]

输出样例

[3, 1, 2]

一道特殊形式的题目——交互题。
题目已经准备好了答案，你可以向题目发起一些格式已给定但数据自定义的问题，根据得到的结果来推出最终答案。
假设已经给前 i - 1 个数字排好了序，你只需要给第 i 个数字确定位置，然后插入进去即可。每个数字插入的询问成本不超过 10。

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> rs;
        rs.push_back(1);
        for(int i=2;i<=N;i++){
            // 值得注意的是，这里 r 可以取到末尾位置，因为实际情况 i 可以插到最后一个
            // 在循环内部，mid = l + r >> 1 永远是下取整，mid不会取到 r
            int l = 0, r = rs.size(); 
            while(l < r) {
                int mid = l + r >> 1;
                if(compare(rs[mid], i)) l = mid + 1;
                else r = mid;
            }
            rs.insert(rs.begin() + l, i);
        }
        return rs;
    }
};