洛谷P1314 聪明的质监员 题解

题目

聪明的质监员

题解

这道题和之前Sabotage G的那道题类似，都是用二分答案求解（这道题还要简单一些，不需要用数学推导二分条件，只需简单判断一下即可）。

同时为了降低复杂度，肯定不能用暴力求解 \(y_{i}\) 的值，很明显这里用到前缀和，到时候计算 \(y_{i}\) 只需用两个前缀和相减一下，再相乘即可。

关于二分区间，这个很明显，若 \(s>y\) ，\(W\) 就二分到左边的区间，否则二分到右边。每选一个 \(W\) 所对应的 \(\left| s-y \right|\) 的值都记录下来，最后选择最小的那个作为答案。复杂度 \(O((m+n)log(w_{max}-w_{min}))\) 。

参考代码

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

#define MAX 200001

typedef long long ll;

int n, m;

ll s;

int w[MAX], v[MAX];

int sec[MAX][2];

ll sum[MAX], sum_v[MAX];

ll res= 1e18;

bool check(int x)

{

	sum[0] = sum_v[0] = 0;

	for(int i=1;i<=n;i++)

		if (w[i] >= x)

		{

			sum[i] = sum[i - 1] + 1;

			sum_v[i] = sum_v[i - 1] + v[i];

		}

		else

		{

			sum[i] = sum[i - 1];

			sum_v[i] = sum_v[i - 1];

		}

	ll y = 0;

	for (int i = 1; i <= m; i++)

		y += (sum[sec[i][1]] - sum[sec[i][0] - 1]) * (sum_v[sec[i][1]] - sum_v[sec[i][0]-1]);

	if (llabs(s - y) < res)

		res = llabs(s - y);

	if (s >= y)

		return 1;

	return 0;

}

int main()

{

	cin >> n >> m >> s;

	for (int i = 1; i <= n; i++)

		scanf("%d %d", &w[i], &v[i]);

	for (int i = 1; i <= m; i++)

		scanf("%d %d", &sec[i][0], &sec[i][1]);

	int l = 0, r = 1000000;

	while (l <= r)

	{

		int mid = (l + r) / 2;

		if (check(mid))//s>y

			r = mid - 1;

		else

			l = mid + 1;

	}

	cout << res;

}

洛谷P1314 聪明的质监员 题解的相关教程结束。