T2-2:勇士的成就
2024-10-01 15:13:25
发布于:天津
第二题
题目大意
题目给出一个长度为的序列,以及变量。
: 指的是你可以进行的操作次数
: 每次操作可以选择几个数字
操作: 你可以选择序列当中的某一个数字进行+1的操作,例如你可以选择一个数字把它变为 。 当的时候,意味着你可以同时指定m个数字进行+1的操作,最多可以执行次
: 我们自己定义出来的一个数字,是否合法需要进行判断,判断的条件如下:
- 在序列当中存在个大于等于的数字
若满足这个条件,那么当前的取值就被称之为合法的。
在你进行操作之后,序列当中可以达到的最大合法为多少?
思路解析
题目既然要求我们去求出一个最大的取值,我们先不管他合不合法,我们先简单的去给他列出一个范围。
我可以注意到题目当中的一个条件: 必须有个大于等于的数字,因此我们可以断定,h的取值最大不可能超过.
我们可以关注到,h=0的时候一定是合法的,因为,无论如何0都是合法的。
那么我们在这里可以发现一个特点,合法的h范围一定为从1开始到达某一个数字的连续序列,例如。
那么我们就可以在范围当中去寻找我们的的取值。
由于我们可以修改其中某些元素的数值,使其+1,我们的目的是通过这样的操作,让更多原本没有到达h的数字变为h。
选择数字进行操作也是有优先级的,比如假如h为10,将一个数字9变为10,和将一个数字1变为10,肯定会优先选9,因为他的消耗小。而我们根据贪心原理,很明显是越多大于等于h的数字越好。
我们可以得到一个贪心原理: 优先修改较大的数字使其变为大于等于h的数字更合理。
序列是无序的,假若为了筛选较大的数字优先进行修改,我们需要使用sort排序使其变为降序,更方便我们进行计算。
更改序列的先后顺序会导致结果产生变化?不会!因为题目要求的条件为大于等于h的数字,跟他的先后顺序没有关系,因此该题的序列更改前后顺序无问题。
根据以上推理,我们来做一下伪代码
- 枚举h的取值
- 判断是否合法
sort(a+1,a+1+n,cmp) ; // 降序给a序列排序下
for(int h = 1 ; h <= n ; h ++ )
{
// 枚举h的取值,判断是否合法
int sum = 0 ; // sum代表加了多少数值
bool flag = true ; // flag代表是否合法
for(int i = 1 ; i <= h ; i ++ )
{
if(h - a[i] > k){ // 判断是否操作可以变为h
flag = false; // 不合法 flag更新为false
break;
}
sum += h - a[i];
// 累加变h的差值
if(sum > k * l){
// k * l为我们最多能够累加的数值
flag = false;
break;
}
}
if(!flag){
cout << h-1 << endl;
// h的合法取值为一个[1~C]的范围,假如碰到第一个不合法的那么前一个一定为最后且最大的合法值。
}
}
但是在,该代码会超时,其时间复杂度为。
时间复杂度优化
列出主要的两部分内容以及目的时间复杂度
- 枚举h的范围,找到最大的h O(n)
- 判断h的合法性,使用操作修改数值。 O(n)
我们可以发现h的取值具有二象性,当当前h取值不合法时,变大绝对不可能找到合法的h,变小才有可能,那么我们要找的h的最大取值一定为合法区间中的C。那么我就可以根据h是否合法,来去写一个二分查找,查找h的取值在其中的合法最值。
#include<bits/stdc++.h>
using namespace std;
long long a[100005];
long long n,m,l,k;
bool cmp(int a,int b){
return a > b;
}
bool check(long long h){
long long sum = 0 ;
// cout << h << endl;
for(int i = 1 ; i <= h ; i ++ )
{
if(a[i] < h )
{
if(h - a[i] > k )return false;
sum += h - a[i];
}
if(sum > k * l){
return false;
}
}
return true; // 查找到合法的数字 返回true
}
int main()
{
cin >> n >> k >> l;
for(int i = 1 ; i <= n ; i ++ )
{
cin >> a[i] ;
}
sort(a+1,a+n+1,cmp);
// 1、二分查找h的取值
int left = 0 ;
int right = n ;
long long answer = 0 ; // 保存最后的答案
while(left <= right)
{
int mid = (left + right) / 2;
if(check(mid)){
// 若合法,提高h取值查找更大合法值
left = mid + 1;
answer = mid ; //保存合法答案
}else {
// 不合法,降低h取值,查找更小的合法值
right = mid - 1;
}
}
cout << answer << endl;
return 0;
}
这里空空如也
有帮助,赞一个