从品牌网站建设到网络营销策划,从策略到执行的一站式服务
Problem - 1622C - Codeforces
给你一个整数数组a1,a2,...,an和整数k。
在一个步骤中,你可以
选择某个索引i并将ai减少1(使ai=ai-1)。
或者选择两个索引i和j,将ai等于aj(使ai=aj)。
为了使数组∑i=1nai≤k的总和,你需要的最小步骤数是什么?(你可以使数组的值为负数)。
输入
第一行包含一个整数t(1≤t≤104)--测试案例的数量。
每个测试用例的第一行包含两个整数n和k (1≤n≤2⋅105; 1≤k≤1015) - 数组a的大小和其总和的上限。
每个测试案例的第二行包含n个整数a1,a2,...,an(1≤ai≤109)--数组本身。
保证所有测试用例的n之和不超过2⋅105。
输出
对于每个测试案例,打印一个整数--使∑i=1nai≤k的最小步骤数。
例子
inputCopy
4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10
输出拷贝
10
0
2
7
注意
在第一个测试案例中,你应该将a1减少10倍以得到低于或等于k=10的和。
在第二个测试案例中,数组a的总和已经小于或等于69,所以你不需要改变它。
在第三个测试案例中,你可以,例如。
设置a4=a3=1。
将a4减少1,得到a4=0。
结果,你会得到数组[1,2,1,0,1,2,1],在1+1=2步中,总和小于或等于8。
在第四个测试案例中,你可以,例如。
选择a7并减少3次;你会得到a7=-2。
选择4个元素a6、a8、a9和a10,它们等于a7=-2。
结果,你会得到数组[1,2,3,1,2,-2,-2,-2,-2,-2],在3+4=7步中,总和小于或等于1。
题解:
首先我们要明白要想操作数最小我们应该怎么做
1.让最小的-1
2.让大的几个数等于最小的
很明显我们应该进行操作1,减到一定数值后再进行操作二最优
关键是我们如何确定要进行多少次操作1呢?
我们发现进行操作2次数顶多n - 1次
那么我们就二分总次数
遍历0~min(n-1,mid)
一部分进行操作1,一部分进行操作2即可
#include#include
#include#include#include
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图