资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

C.SetorDecrease(二分+有两个不确定情况如何二分)-创新互联

Problem - 1622C - Codeforces

创新互联公司是网站建设技术企业，为成都企业提供专业的网站设计制作、网站制作，网站设计，网站制作，网站改版等技术服务。拥有10余年丰富建站经验和众多成功案例，为您定制适合企业的网站。10余年品质，值得信赖！

给你一个整数数组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#include#includeusing namespace std;
#define int long long
int a[200050];
int b[200050];
int n,k;
int check(int x)
{
	for(int i = 0;i<= min (x,n-1);i++)//进行操作2的次数
	{
		int mi = a[n] - (x-i);//(x-i)为进行操作1的次数
		int s = b[n-1] - b[i] + (i+1)*(mi);//i+1是前面i个数,是根据第n个数变化的
		if(s<= k)
		return 1; 
	}
	return 0;
}
void solve()
{
	cin >>n >>k;
	int s = 0;
	for(int i = 1;i<= n;i++)
	{
		cin >>a[i];
		s += a[i];
	}
	sort(a+1,a+1+n,greater());
	for(int i = 1;i<= n;i++)
	b[i] = b[i-1] + a[i];
	if(s<= k)
	{
		cout<<"0\n";
		return ;
	}
	int l = 0,r = s - k;
	while(l<= r)
	{
		int mid = (l + r)/2;
		if(check(mid))
		{
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	cout<< l<<"\n";
}
signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	int t = 1;
	cin >>t;
	while(t--)
	{
		solve();
	}
}

//1 10 11

//001
//010
//011
//100

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


文章标题：C.SetorDecrease(二分+有两个不确定情况如何二分)-创新互联
分享URL：http://cdkjz.cn/article/djjdgd.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
UI设计外贸营销网站建设都江堰做网站seo推广公司青羊总部基地成都棕树机房关键词优化兴宏源活动板房成都定制网站建设香港云服务器租用

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图