【luogu P1314 聪明的质监员】 题解

题目链接：https://www.luogu.org/problemnew/show/P1314

二分答案

但是计算区间贡献的时候 直接暴力会挂

前缀和加速

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define ll long long

using namespace std;

const int maxn = 2000000 + 10;

ll w[maxn], v[maxn], pren[maxn], prev[maxn], l[maxn], r[maxn], n, m, S;

ll maxw = -9999999999999, minw = 9999999999999, ans = 9999999999999, now;

bool check(int W)

{

	ll Y = 0;

	memset(pren, 0, sizeof(pren));

	memset(prev, 0, sizeof(prev));

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

	{

		if(w[i] > W) pren[i] = pren[i-1] + 1, prev[i] = prev[i-1] + v[i];

		else pren[i] = pren[i-1], prev[i] = prev[i-1];

	}

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

	Y += (pren[r[i]] - pren[l[i]-1])*(prev[r[i]] - prev[l[i]-1]);

	now = abs(Y-S);

	if(Y > S) return true;

	return false;

}

int main()

{

	scanf("%lld%lld%lld",&n,&m,&S);

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

	{

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

		maxw = max(w[i], maxw);

		minw = min(w[i], minw);

	}

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

	scanf("%lld%lld",&l[i],&r[i]);

	ll left = minw - 1, right = maxw + 2, mid;

	while(left <= right)

	{

		int mid = (left + right)>>1;

		if(check(mid)) left = mid + 1;

		else right = mid - 1;

		if(ans > now) ans = now;

	}

	printf("%lld",ans);

}

【luogu P1314 聪明的质监员】 题解的相关教程结束。