题目描述
输入格式
输出格式
输出一行仅一个整数，表示建造的信号传输通道最大的优质指数。如果无解，输出-1。
输入样例:
11 12 1 2 1 2 6 2 1 2 1 2 1
输出样例:
2
题意
在不低于 W WW 的满意度下，使得两信号站之间距离最大。
即：给你一个数组，选 x xx 个位置之和 ≥ W \geq W≥W，求相邻两位置的间隔的最大值。
思路
代码：
int n, w; int a[N], f[N]; bool check(int x) { memset(f, 0, sizeof f); for (int i = 1; i <= n ;i++) { f[i] = f[i - 1]; if (i >= x && i <= n - x + 1) f[i] = max(f[i], f[i - x] + a[i]); } return f[n] >= w; } void solve() { cin >> n >> w; int sum = 0; for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i]; if (sum < w) { cout << -1 << endl; return ; } // 特判 -1 if (w == 0) { cout << n + 1 << endl; return ; } // 特殊的 w==0 int l = 1, r = n; while (l < r) { int mid = l + r + 1 >> 1; if (check(mid)) l = mid; else r = mid - 1; } cout << l << endl; }
