首页 > 其他分享 >C. Add, Divide and Floor

C. Add, Divide and Floor

时间:2024-05-01 10:33:05浏览次数:24  
标签:cnt Divide Floor int Add cin ++ xx include

链接:https://codeforces.com/problemset/problem/1901/C
洛谷链接:https://www.luogu.com.cn/problem/CF1901C
思路:
首先去重:这里建议分清楚总操作数n和元素总数cnt。
然后把去重的元素放在数组中,sort让它升序,取两个极端的差。(因为中间的数会被并到里面去,就是说,可以理解为区间收缩)
分为两步:
①计数:2^k≤delta的时候,k++,意味着要多少次;
②写每次的数:当k≤n时,就可以左偏取数,注意最后一个特判:当差为1的时候,即:left = right - 1,取最后一次的为right + 1(因为是左偏),所以完成
代码:

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
#include<set>
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
int lst[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		int n; cin >> n;
		map<int, bool>mp;
		int cnt=0;
		int xx;
		for (int i = 0; i < n; i++)
		{
			cin >> xx;
			if (!mp[xx])
			{
				mp[xx] = 1;
				lst[cnt] = xx;
				cnt++;
			}
		}
		if (n == 1 or cnt == 1) { cout << '0' << endl; continue; }
		sort(lst, lst + cnt);
		int minn = lst[0], maxn = lst[cnt - 1];
		int delta = maxn - minn;
		int k = 1; int kpp = 2;
		while (kpp <= delta)
		{
			kpp <<= 1;
			k++;
		}
		cout << k << endl;
		if (k <= n)
		{
			while (minn + 1 < maxn)
			{
				int mid = minn + (maxn - minn + 1) / 2;
				cout << mid;
				minn = (minn + mid) / 2, maxn = (maxn + mid) / 2;
				
				if (minn + 1 <= maxn)cout << ' ';
			}
			cout << maxn + 1 << endl;
		}
	}
	return 0;

}

标签:cnt,Divide,Floor,int,Add,cin,++,xx,include
From: https://www.cnblogs.com/zzzsacmblog/p/18169063

相关文章

  • ES Validation Failed: 1: this action would add [1] shards, but this cluster c
    [2024-05-01T08:56:52,606][ERROR][o.e.x.i.IndexLifecycleRunner][tools]policy[ilm-history-ilm-policy]forindex[.ds-ilm-history-5-2024.03.28-000001]failedonstep[{"phase":"hot","action":"rollover","name&qu......
  • public void add(int index, E element)的方法源码分析
    publicclassArrayList<E>extendsAbstractList<E>implementsList<E>,RandomAccess,Cloneable,java.io.Serializable{publicvoidadd(intindex,Eelement){rangeCheckForAdd(index);//校验数组是否越界......
  • paddlepaddle自定义网络模型及onnx模型转换与推理
    前面介绍过了使用Paddleseg套件训练后,使用export.py文件导出模型为推理部署模型。具体可以参考之前的:https://www.cnblogs.com/wancy/p/18028138本文介绍使用paddle自定义简单二分类CNN模型到训练数据集再到转换onnx模型推理。1. 数据集划分我这里将数据划分为tr......
  • notepadd++下载
    现在网上下载个软件越来越麻烦了,各种广告各种隐藏陷阱。为了大家以后能更快速的下载到正版的notepad++这里上传到git做了备份 下载地址: https://gitee.com/liu_chaos/notepad-8.5.3-official-version/blob/master/Notepad_downloader.8.5.3.exe ......
  • ABC 288 D - Range Add Query
    题目链接:设\(a[i]\)表示下标对\(k\)取模为\(i\)的所有数的和。那每次操作就是将数组\(a\)的所有数都加\(c\)。最终为\(0\)的充分必要条件就是\(a\)的所有数都是一样的。因此,对于每组询问,统计\([l,r]\)中数字下标对\(k\)取模的所有数的和,看看是否为同一个数即可......
  • 题解:P10329 [UESTCPC 2024] Add
    Add题意将序列进行一系列的操作,输出对\(a_{1}\)的期望值。题目中操作说的比较明了,再次就不特殊声明了。思路据题意所知,每一个\(n\)应该对应了一个固定的答案。于是我就想到可以打表,就打出了下面的式子。n=1时ans=1n=2时ans=5n=3时ans=14n=4时ans=30n=5时ans=5......
  • PaddleSeg2.8训练验证时报错[Hint: Expected axis >= -rank && axis < rank == true,
    1.报错问题ValueError:(InvalidArgument)Theaxisisexpectedtobeinrangeof[0,0),butgot0[Hint:Expectedaxis>=-rank&&axis<rank==true,butreceivedaxis>=-rank&&axis<rank:0!=true:1.]2.解决办法上述报错问题是在......
  • Web Component addEventListener .bind(this)的函数带参数引起的报错
     一开始这样写:  this.shadowRoot.querySelector('.prev').addEventListener('click',this.moveSlide(1).bind(this));报错:UncaughtTypeError:Cannotreadpropertiesofundefined(reading'bind')    以为是前面的DOM获取不对,但是怎么改都不对,网上查询后......
  • CF1634F Fibonacci Additions
    Statement:给出两个长度为\(n\)的序列\(a,b\),每次在\(a\)或\(b\)上\([l,r]\)操作,一次操作将会使\([l,r]\)中的数分别加上\(fib[1],fib[2]...,fib[r-l+1]\),每次操作完询问\(a,b\)是否在模\(mod\)意义下相等。Solution:先简化问题,令\(c_i=a_i-b_i\),问题......
  • doublelist_add
    双向链表的插入操作的相关操作1.头部插入/******************************************************************************函数名称: HeadAdd*函数功能:双向链表的头部插入*函数参数:*@a:*He......