q2. 因为当 \(cnt - 1 > len / 2\) 时，必然存在一个大于 \(x\) 的数满足 \(cnt - 1 = len / 2\)，所以需要返回 \(true\) 以向上改变二分区间
我们可以枚举区间右端点，并选定左端点以使式子的结果为 \(true\)
定义 \(sum[i]\) 为序列的前缀和，\(L\) 为当前区间的左端点 \(-1\) , \(R\) 为当前区间的右端点
那么 \(cnt = sum[R] - sum[L]\) , \(len = R - L\)
于是式子可以转变为 \(sum[R] - sum[L] - 1 >= (R - L) / 2\)
通过移项 ，式子可变为 \(2 × sum[R] - R - 2 >= 2 × sum[L] - L\)
因为 \(R\) 是我们枚举的 , 所以 \(R、sum[R]\) 都可认为常数
为了让不等式成立，我们需要让不等号右边的式子尽可能小
所以我们要取 \(mi\) \(=\) \(min∑(2 * sum[i] - i) , i ∈[1 , i - k]\)
因为每枚举一个右端点，只会出现一个新的可以选择的左端点 \(i-k\)
所以 \(mi\) 对于每一个右端点只要 \(O1\) 就可以得到了
注意：
得到了 \(mi\) 我们不能直接改写式子为 \(2 × sum[R] - R - 2 >= mi\)
因为 \((4 - 1) / 2 = 1\) 而不是 \(1.5\)
所以我们还要维护两个变量分别代表 \(sum[L]\) 和 \(L\)
AC_Code #include<bits/stdc++.h> using namespace std; const int N = 3e5 + 10; int n , m , k , a[N] , b[N] , sum[N]; bool check(int x) { int mi = 1e9 , pre = 1e9 , pos = -1e9; for(int i = 1 ; i <= n ; i ++) { if(a[i] >= x) b[i] = 1; else b[i] = 0; sum[i] = sum[i - 1] + b[i]; if(i - k >= 0 && mi >= 2 * sum[i - k] - (i - k)) { mi = 2 * sum[i - k] - (i - k); pos = i - k; pre = sum[i - k]; } if(sum[i] - pre - 1 >= (i - pos) / 2) return true; } return false; } signed main() { cin >> n >> k ; for(int i = 1 ; i <= n ; i ++) cin >> a[i]; int l = 1 , r = n , res = 0; while(l <= r) { int mid = l + r >> 1; if(check(mid)) l = mid + 1 , res = mid; else r = mid - 1; } cout << res << '\n'; return 0; } E. Paired Payment 题目链接点我跳转
题目大意给定一张包含 \(N\) 个点，\(M\) 条边的无向图，每条边都有它的权值 \(w\) \((1 <= w <= 50)\)
每次从一个节点出发，都必须走完两条边才能停下(中间经过的点不算到达过)
途中的花费为两条边权值的和的平方
问节点 \(1\) 出发到达每个点所需的最小花费分别为多少
解题思路很多人用暴力的做法居然没有 \(fst\) ？这就很神奇 \(hhh\)
update： 大数据貌似在 \(fst\) 之后才加上
定义 \(ans[i]\) 表示从节点 \(1\) 出发到达节点 \(i\) 的最小花费
定义 \(dis[w][i]\) 表示从某个点 \(x\) 走了 一条权值为 w 的边 到达节点 \(i\) ，而 \(dis[w][i] = min(ans[x])\)
假设当前节点为 \(u\) , 它的相邻节点为 \(v\) , 它们之间的边权为 \(w\)
那么不难得到
dis[w][v] = min(dis[w][v] , ans[u]);for(int j = 1 ; j <= 50 ; j ++) ans[v] = min(ans[v] , dis[j][u] + (j + w) * (j + w));
所以跑 \(dijkstra\) 时只要边权被更新我们就把该点入队
但是传统的 \(dijkstra\) 在一个点入队后就会被打上标记从此不能再入队了
而这里我们显然是需要一个点重复入队才能保证答案的最优
如果选择重复入队就会使得复杂度爆炸？那怎么办呢？
我们可以统计每个点入队的次数，当次数大于 \(50\) 时就不再入队
这样可行是因为 \(dis\) 是由 \(ans\) 更新 , \(ans\) 是由 \(ans\) 和 边权 更新