CF613B Skills

题目大意：

定义

sum

为等级为

A

的技能数量，

level

为所有技能里面的最低等级。

给出了

n

个技能等级，和

m

次让技能等级升

1

的加点，限制满级为

A

。以及系数

cf

和

cm

。

我们需要求出

m

次加点之后，

sum \times cf + level \times cm

的最大值。

做法

暴力枚举 + 二分套二分

我们可以发现只有最低等级和最大等级

A

的技能会对最后的答案产生贡献。所以我们可以暴力枚举其中一个，那么另一个可以通过剩下的加点次数求出。

下方只讲枚举

A

数量的做法。

因为考虑的是等级的大小，所以我们先将 $a$ 数组从小到大排序。

我们先预处理一个前缀和数组， $pre_i$ 记录前面所有的技能都变成 $a_i$ 时所需的加点数（后面会用到）。
我们从第 $n$ 个数到第 $1$ 个数枚举。
然后我们如何求出可以满足的最低等级呢？从第 $0$ 开始枚举显然时间复杂度太劣，考虑优化。

因为升的等级越高所需的加点越多，这是一个单增的函数，所以我们可以二分查找满足条件的最大等级。
我们再继续考虑二分具体如何实现。

二分上下界为给定的等级限制 $l = 0,r = A$ 。

我们需要在该等级下，找到所有小于等于该等级的数，再进行所需加点数量的判断。这又如何处理？

这就是很板的二分了，因为我们的 $a$ 数组已经是有序的，所以我们直接在数组上进行二分查找第一个不大于该等级的数。

根据我们预处理的前缀和数组，可以快速求出该等级所需要的加点数，与 $m$ 进行判断就好了。
我们在枚举过程中选取其中的最大值并记录 $A$ 的数量和 $level$ 的大小就行了。

时间复杂度

O(n\log^2n)

，~~比较卡~~，但可以通过此题。

代码

这个做法其实比较暴力了，但非常好想，代码实现上细节较多。

代码比较冗余，请读者自行参考。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
struct Node{
	int sum;
	int id;
}a[N];
int ta[N];
int pre[N];

int n, tn;
int A;
int cf, cm;
int m;
int tot;
int ans;
int ansl, ansa;

bool chk(int x, int sum){
	if (a[x].sum < sum)	return true;
	else				return false;
}

bool check(int x){
	
	int l = 1, r = tn;
	
	while(l < r){
		int mid = (l + r) >> 1;
		if (chk(mid, x)) l = mid + 1;
		else			 r = mid;
	}
	
	l -= 1;
	
	if (pre[l] + (x - a[l].sum) * l + tot <= m) return true;
	else										return false;
}

void init(){
	for (int i = 1; i <= n; i++){
		pre[i] = pre[i - 1];
		pre[i] += (i - 1) * (a[i].sum - a[i - 1].sum);
	}
	
	return;
}

bool cmp(Node x, Node y){
	return x.sum < y.sum;
}

signed main(){
	scanf("%lld", &n);
	scanf("%lld", &A);
	scanf("%lld%lld", &cf, &cm);
	scanf("%lld", &m);
	
	for (int i = 1; i <= n; i++){
		scanf("%lld", &a[i].sum);
		a[i].id = i;
	}
	
	sort(a + 1, a + 1 + n, cmp);
	
	n++;
	a[n].sum = A;
	
	ansa = n;
	
	init();
	
	for (int i = n; i >= 1; i--){
		tot += A - a[i].sum;
		
		if (tot > m) break;
	
		tn = i;
		
		int l = 0, r = A;
		while(l < r){ 
			int mid = (l + r + 1) >> 1;
			if (check(mid)) l = mid;
			else			r = mid - 1;
		}
		
		if (ans < (n - i) * cf + l * cm){
			ans = (n - i) * cf + l * cm;
			ansl = l;
			ansa = i;
		}
	}	
	
	for (int i = 1; i < n; i++){
		if (a[i].sum < ansl) a[i].sum = ansl;
	}
	
	for (int i = ansa; i < n; i++){
		a[i].sum = A;
	}
	
	for (int i = 1; i < n; i++){
		ta[a[i].id] = a[i].sum;
	}
	
	printf("%lld\n", ans);
	for (int i = 1; i < n; i++){
		printf("%lld ", ta[i]);
	}
	
	return 0;
}

题解：CF613B Skills

文章操作

CF613B Skills

题目大意：

做法

暴力枚举 + 二分套二分

代码

相关推荐

评论

题解：CF613B Skills