最佳牛围栏（实数二分、前缀和、双指针、区间平均值判断）

//https://www.acwing.com/problem/content/description/104/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>

typedef long long ll;

using namespace std;

const int N = 1e5 + 10;

int n, f;
double l, r;
int a[N];
double s[N];

bool calc(double avg)
{
	for (int i = 1; i <= n; i++)	s[i] = s[i - 1] + a[i] - avg;

	double mins = 0x3f3f3f3f;
	for (int i = 0, j = f; j <= n; i++, j++)
	{
		mins = min(mins, s[i]);

		if (s[j] - mins >= 0)	return true;
	}

	return false;
}

int main()
{
	cin >> n >> f;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		r = max(r, (double)a[i]);
	}

	while (r - l > 1e-5)
	{
		double mid = (l + r) / 2;
		if (calc(mid))	l = mid;
		else r = mid;
	}

	cout << (int)(r * 1000) << endl;

	return 0;
}

二分答案区间，答案可能的范围是[0，max(a[i])]。

属于实数二分，关键在于check函数的写法。

首先，我们将a数组中所有的数减去avg。这样，大于0的数即大于平均值的数，小于0的数即小于平均值的数。只需要判断前缀和是否大于0，即可判断这些数是否大于avg。
使用双指针继续优化，初始令i=0，j=f，每次循环i++，j++，保证i和j的距离至少是f。关键在于定义变量保存a[i]的最小值，这个最小值到j的距离大于等于f。我们只需要判断a[j] - mins是否大于0，即可判断是否存在长度大于等于f的区间平均值大于等于avg。

特殊排序（二分插入排序、交互式）

//https://www.acwing.com/problem/content/115/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> ans;

        ans.push_back(1);
        for (int i = 2; i <= N; i++)
        {
            int l = 0, r = ans.size() - 1;
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (compare(ans[mid], i))    l = mid + 1;
                else r = mid - 1;
            }

            ans.push_back(i);
            for (int j = ans.size() - 2; j > r; j--) swap(ans[j], ans[j + 1]);
            if (!compare(ans[r], i)) swap(ans[r], ans[r + 1]);
        }

        return ans;
    }
};