题目:
代码:
#include<iostream>
using namespace std;int sa[125][125];/*
二分思想:
s=0,全计算,y大,且s小,所以不行
s=oo ,全不过,y小,但s大,所以不行于是我们取mid,根据结果取区间前缀和思想:
求w的价值之和时
*/#define M 200005
int v[M];
int w[M];
int l[M];
int r[M];
long long pre_n[M],pre_v[M];
long long Y,s,sum;
int n,m,mx=-1,mn=2147483647;//给标准s,计算y(每个标准都有一个y)
bool check(int W)
{for(int i=1;i<=n;i++){//计算yi//大于标准,计算if(w[i]>W){//本项结果为1,上一项为n[i-1],同时完成了前缀和和传入的任务pre_n[i]=pre_n[i-1]+1;pre_v[i]=pre_v[i-1]+v[i];}//小于标准,忽略else{pre_n[i]=pre_n[i-1];pre_v[i]=pre_v[i-1];}}//计算s(前缀和使用)for(int i=1;i<=m;i++){//每一个yi对应了pre——n和pre——v这两个前缀和Y+=(pre_n[r[i]]-pre_n[l[i]-1])*(pre_v[r[i]]-pre_v[l[i]-1]);}//在下面每有一次循环就算一次,传到全局sum=llabs(Y-s);//用于二分if(Y>s){return 1; }else{return 0;}}int main()
{//n为矿石数目,m为区间数目,s为重量标准int n,m,s;cin>>n>>m>>s;//v和w分别输入for(int i=1;i<=n;i++){cin>>v[i]>>w[i];//记录最值,方便二分mx=max(w[i],mx);mn=min(w[i],mx);}for(int i=1;i<=m;i++){//存储区间cin>>l[i]>>r[i];}//s的上下界int left=mn-1;int right=mx+2;int mid;long long ans=0x3f3f3f3f3f3f3f3f;//二分查找while(left<right){//相当于除以二,防止left+right太大导致崩溃mid=(left+right)/2;//循环二分查找,当mid为标准时//用sum传出目标,从而计算最小值//返回左右关系,从而修改二分区间//传回左右关系if(check(mid)){left=mid+1;}else{right=mid-1;}//传回大小if(sum<ans){ans=sum;}}cout<<ans<<endl;}