洛谷P1314

常规
1

求各位红名巨佬帮帮我
二分+前缀和，时间不超了，听取WA声一片

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200005;
ll n, m, maxx;
ll s, y, ans, res=0x3f3f3f3f;
struct node
{
	ll w, v;
} a[N];
struct qj
{
	ll s, e;
} b[N];
ll sn[N],sv[N];
ll minn; 
bool count(ll W)
{
	ans = 0;
	memset(sn,0,sizeof(sn));
	memset(sv,0,sizeof(sv));
	for(int i=1;i<=n;i++){
		if(a[i].w>=W){
			sn[i]=sn[i-1]+1;
			sv[i]=sv[i-1]+a[i].v;
		}
		else{
			sn[i]=sn[i-1];
			sv[i]=sv[i-1];
		}
	}
	for (ll i = 1; i <= m; i++)
	{
		ll st=b[i].s,en=b[i].e;
		ans+=(sn[en]-sn[st-1])*(sv[en]-sv[st-1]);
	}
	res=min(res,llabs(ans-s));
	return ans>s;
}
int main()
{
	scanf("%d%d%lld", &n, &m, &s);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", &a[i].w, &a[i].v);
		maxx = max(maxx, a[i].w);
	}
	for (int i = 1; i <= m; i++)
		scanf("%d%d", &b[i].s, &b[i].e);
	ll l = 1, r = maxx, mid;
	while (l <= r)
	{
		mid = (l+r) / 2;
		if (count(mid))
			l=mid+1;
		else
			r=mid-1;
	}
	printf("%d",res);
}
3 个赞
2

普及+/提高……

2 个赞
3

还好我一个朋友写过：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt,k,sum,c[200001],d[200001],a[200001],b[200001],x[200001],y[200001],n,m,mx=-1,my=INT_MAX,ans=LONG_LONG_MAX;
bool f(int kuang){	
	cnt=0,sum=0;
	memset(c,0,sizeof(c));
	memset(d,0,sizeof(d));
	for(int i=1;i<=n;i++){
		if(a[i]>=kuang) c[i]=c[i-1]+1,d[i]=d[i-1]+b[i];
		else c[i]=c[i-1],d[i]=d[i-1];
	}
	for(int i=1;i<=m;i++){
		cnt+=(c[y[i]]-c[x[i]-1])*(d[y[i]]-d[x[i]-1]);
	}
	sum=llabs(cnt-k);
	return cnt>k;
	
}
signed main(){
	cin>>n>>m>>k; 
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		mx=max(mx,a[i]);
		my=min(my,a[i]);
	}
	for(int i=1;i<=m;i++){
		cin>>x[i]>>y[i];
	}
	int l=my-1,r=mx+2;
	while(l<=r){
		int mid=(l+r)>>1;
		if(f(mid)){
			l=mid+1;
		}
		else{
			r=mid-1;
		}
		if(sum<ans){
			ans=sum;
		}
	}
	cout<<ans;
}
2 个赞
4

但我是绿名蒟蒻

2 个赞