Yuilice的题解

题目大意

给出$n$个元素，每个元素有两个属性$w_i,v_i$，分别代表增加减少的闸值和增减数量。

你可以选定一个数字$S$作为每一个元素的闸值，假如$S>= w_i$，那么你将获得$v_i$点价值，否则减少$v_i$价值。

求出总价值$sum_v >= M$的最小$S$取值。

思路分析

找单调性，很快可以发现$S$是与$Sum_v$成正比关系的，$S$的数值越大，那么$Sum_v$的数值也会相应的变大。

那么就可以针对于$S$来进行二分，使得$Sum_v >= M$的同时，让$S$的数值尽可能地小，针对于$S$的区间来进行不停进行范围的枚举，直到满足要求为止。

可能会出现两种情况

1. $S -> Sum_v < M$ :此时说明$S$的数值不足以达到目标，让$S$变大即可。
2. $S -> Sum_v >= M$ : 此时说明$S$的数值已经达到目标，但是不一定是最小值，可能是之一，那么保存S继续缩短范围。

总计两步

1. 使用二分得出合理的$S$ ，时间复杂度为$Log(n)$
2. 使用枚举遍历$n$求得$Sum_v$，时间复杂度为$O(n )$

时间复杂度分析

$O(nlog(n))$

代码示范

#include<bits/stdc++.h>
using namespace std;
long long n,m;

struct Node{
	long long w,v;
}a[2000005];

bool check(long long x){
	long long sum = 0;
	
	for(int i = 1 ; i <= n ; i ++ ){
		if(a[i].w <= x){
			sum += x / a[i].w * a[i].v;
		}else {
			sum -= a[i].v;
		}
	}
	
	return sum >= m;
}

int main()
{
	cin >> n >> m ;
	for(int i = 1 ; i <= n ; i ++ ){
		cin >> a[i].w;
	}
	for(int i = 1 ; i <= n ; i ++ )
	{
		cin >> a[i].v;
	}
	long long left,right,answer;
	left = 0;
	right = 1e9+7;
	answer = 0;
	while(left <= right){
		long long mid = left + right >> 1;
		if(check(mid)){
			answer = mid;
			right = mid - 1;
		}else {
			left = mid + 1;
		}
	}
	cout << answer << endl;
	return 0;
}

—— Yuilice