[传送门](P1314 [NOIP 2011 提高组] 聪明的质监员 - 洛谷)
分析
1.W变大，则要求条件更严格，则sigema（y)不增，具有单调性，考虑二分查找W。O（log w）
2.对于每一个W，可以处理前缀和求特征值。O(n+m)
3.总时间复杂度O(log w * (n+m) )
代码实现
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mid ((r+l)>>1)
const int N = 2 * 1e5+10;
ll s;
int n, m, W;
ll w[N], v[N], sum[N], is[N];
int L[N], R[N];
void doit(int We)
{memset(sum, 0, sizeof(sum));memset(is, 0, sizeof(sum));for (int i = 1; i <= n; i++){int tmp = (w[i] >= We);sum[i] = sum[i - 1] + tmp * v[i];is[i] = is[i - 1] + tmp;}
}
ll Y()
{ll y = 0;for (int i = 1; i <= m; i++)y += (sum[R[i]] - sum[L[i] - 1]) * (is[R[i]] - is[L[i] - 1]);return y;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m >> s;int maxw = -1, minw = 1e9;for (int i = 1; i <= n; i++)cin >> w[i] >> v[i], maxw = max((long long)maxw, w[i]), minw = min((long long)minw, w[i]);for (int i = 1; i <= m; i++)cin >> L[i] >> R[i];ll ans = 1e15;ll yy;int l = minw - 1, r = maxw + 1;while (r >= l){doit(mid);yy = Y();if (yy > s)l = mid + 1, ans = min(ans, abs(yy - s));else if (yy < s)r = mid, ans = min(ans, abs(yy - s));else{cout << 0;return 0;}if (r == l){cout << ans;return 0;}}ans = min(ans, abs(yy - s));cout << ans;return 0;
}
Trick/错误总结
-
注意W的取值范围应该是maxw+1到minw-1之间 不要把范围搞小了
-
注意mid是下取整，故二分查找时若更新l，应令l=mid+1，否则无限循环。
-
l==r的判断放到最后