AcWing 102. 最佳牛围栏 原题链接
农夫约翰的农场由 NN 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 FF 块地，其中 FF 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
输入格式
第一行输入整数 NN 和 FF ，数据间用空格隔开。
接下来 NN 行，每行输入一个整数，第i+1i+1行输入的整数代表第ii片区域内包含的牛的数目。
输出格式
输出一个整数，表示平均值的最大值乘以1000再 向下取整 之后得到的结果。
数据范围
1≤N≤1000001≤N≤100000 1≤F≤N1≤F≤N
输入样例：
10 6
6
4
2
10
3
8
5
9
4
1
输出样例：
6500
题目思路
static int[] arr;
static double[] sum;
static int n;
static int f;
private static boolean check(double avg) {
for (int i = 1; i < n + 1; i++) {
sum[i] = sum[i - 1] + arr[i - 1] - avg;
}
double min = Double.MAX_VALUE;
for (int r = f; r < n + 1; r++) {
min = Math.min(min, sum[r - f]);
if (sum[r] - min >= 0) return true;
}
return false;
}
public static void main(String[] args) {
n = in.nextInt();
f = in.nextInt();
arr = new int[n];
sum = new double[n + 1];
in.nextIntegerArray(arr);
double l = 1d;
double r = 2000d;
while (r - l > 1e-5) {
double mid = (l + r) / 2;
if (check(mid)) {
l = mid;
} else {
r = mid;
}
}
out.println((int)(r * 1000));
out.flush();
out.close();
}
AcWing 113. 特殊排序 原题链接
有N个元素，编号1.2..N，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。
注意：不存在两个元素大小相等的情况。
也就是说，元素的大小关系是N个点与N*(N-1)/2条有向边构成的任意有向图。
然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过10000次提问来获取信息，每次提问只能了解某两个元素之间的关系。
现在请你把这N个元素排成一行，使得每个元素都小于右边与它相邻的元素。
你可以通过我们预设的bool函数compare来获得两个元素之间的大小关系。
例如，编号为a和b的两个元素，如果元素a小于元素b,则compare（a,b）返回true，否则返回false。
将N个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。
数据范围
1≤N≤10001≤N≤1000
输入样例
[[0, 1, 0], [0, 0, 0], [1, 1, 0]]
输出样例
[3, 1, 2]
题目思路
// The compare API is defined in the parent class Relation:
// boolean compare(int a, int b);
// return boolean means whether a is less than b.
public int[] specialSort(int n) {
List<Integer> list = new ArrayList<>();
list.add(1);
for (int i = 2; i <= n; i++) {
int l = 0;
int r = list.size() - 1;
while (l < r) {
int mid = l + r + 1 >> 1;
if (compare(list.get(mid), i)) {
l = mid;
} else {
r = mid - 1;
}
}
// 当满足条件时，将i插入到l+1位置
if (compare(list.get(l), i))
list.add(l + 1, i);
//不符合条件时，说明找不到一个比他小的数
//即他本身就是最小的数，此时把他插入到开头位置
else list.add(0, i);
}
int[] res = new int[n];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}