网站备案号查不到,小型个人网站制作,深圳建筑设计公司排名榜,网站建设分金手指专业二五题目链接:传送门 题目大意:给你n个物品#xff0c;每件物品有重量 W 和价值 V#xff0c;给m个区间#xff0c;和一个标准值。(n,m最大200000) 要求找到一个值x#xff0c;使得m个所有区间的权值和与标准值的差的绝对值最小。单个区间权值计算公式(数目num0#xff0c;价值…题目链接:传送门 题目大意:给你n个物品每件物品有重量 W 和价值 V给m个区间和一个标准值。(n,m最大200000) 要求找到一个值x使得m个所有区间的权值和与标准值的差的绝对值最小。单个区间权值计算公式(数目num0价值sum0,若满足 Wi x ,则numsumVi) 单个区间权值为num*sum 题目思路: 二分前缀和 首先权值和与X是递减关系X越大所得值越小我们容易想到二分但是m个区间的比较判断怎么处理如果直接模拟复杂度最大可达 n^2logn 显然不行 其实我们可以用前缀和的想法用一个数组num 表示1~i 满足Wx的个数sum对应为满足条件的W对应的V之和那么对于区间我们可直接O1得值 每次前缀处理On 所以总复杂度 nlogn 还有此题需用long long 不然WA #include iostream
#include cstdio
#include cstdlib
#include cmath
#include algorithm
#include cstring
#include stack
#include cctype
#include queue
#include string
#include vector
#includefunctional
#include set
#include map
#include climits
#define lson root1,l,mid
#define rson root1|1,mid1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 200005
#define maxn 10000500
typedef pairint,int PII;
typedef long long LL;LL n,m;
LL k,sta,l-1,r,ans1ll62;
struct Node{LL x,v;
}node[N];
struct Seg{LL x,y;
}seg[N];
LL num[N],sum[N];
bool match(LL x){for(LL i1;in;i){num[i]num[i-1];sum[i]sum[i-1];if(node[i].xx){num[i];sum[i]node[i].v;}}LL temp0;for(LL i1;im;i){LL t1seg[i].x,t2seg[i].y;temp(sum[t2]-sum[t1-1])*(num[t2]-num[t1-1]);}temptemp-sta;ansmin(ans,llabs(temp));return temp0;
}
int main(){LL i,j,v;scanf(%lld%lld%lld,n,m,sta);for(i1;in;i){scanf(%lld%lld,node[i].x,node[i].v);rmax(r,node[i].x);}for(i1;im;i){scanf(%lld%lld,seg[i].x,seg[i].y);}r;while(lr){LL midlr1;if(match(mid)){lmid1;}else rmid-1;}printf(%lld\n,ans);return 0;
} 转载于:https://www.cnblogs.com/Kurokey/p/5684452.html
