首页 > 其他分享 >Codeforces Round 924 (Div. 2)B. Equalize(思维+双指针)

Codeforces Round 924 (Div. 2)B. Equalize(思维+双指针)

时间:2024-02-12 21:12:06浏览次数:33  
标签:int rep Codeforces long Equalize front Div define

目录

题面

image

链接

B. Equalize

题意

给一个数组\(a\),然后让你给这个数组加上一个排列,求出现最多的次数

题解

赛时没过不应该。
最开始很容易想到要去重,因为重复的元素对于答案是没有贡献的。
去重后排序。,然后维护一个极差小于n-1的区间,,区间长度就是可能的答案。
可以用双指针去实现。

代码

#include <bits/stdc++.h> 
#define int long long
#define rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define fep(i,a,b) for(int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define pll pair<long long, long long>
#define ll long long
#define db double
#define endl '\n'
#define x first
#define y second
#define pb push_back

using namespace std;
const int N=1e5+10;


void solve()
{
	int n;cin>>n;
	vector<int>a(n+1);
	rep(i,1,n){
		cin>>a[i];
	}
	sort(a.begin()+1,a.end());
	set<int>s;
	deque<int>q;
	int ans=0;
	rep(i,1,n){
		while(q.size()&&a[i]-a[q.front()]>=n){
			s.erase(a[q.front()]);
			q.pop_front();
		}
		q.pb(i);
		s.insert(a[i]);
		int t=s.size();
		ans=max(ans,t);
	}
	cout<<ans<<endl;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//   	freopen("1.in", "r", stdin);
  	int _;
	cin>>_;
	while(_--)
	solve();
	return 0;
}

标签:int,rep,Codeforces,long,Equalize,front,Div,define
From: https://www.cnblogs.com/cxy8/p/18014121

相关文章

  • div 除法指令
    DIV(unsigneddivide)无符号数除法被除数的位数取决于除数格式:DIVSRC操作:SRC为字节时,商=(AL)←(AX)/(SRC),余数=(AH)←(AX)/(SRC)SRC为字时,商=(AX)←(DX,AX)/(SRC),余数=(DX)←(DX,AX)/(SRC)—————......
  • Codeforces Round 924 (Div. 2)
    E-ModularSequence题意给定\(n,x,y,s\),求是否有长为\(n\)的一个数列\(\{a\}\)满足\(a_1=x\)且\(\foralli>1:a_i=a_{i-1}+y\lora_i=a_{i-1}\bmody\)且\(\sum\limits_{i=1}^{n}a_i=s\)。\(\sumn,\sums\le2\times10......
  • Codeforces Round 924 (Div. 2)
    不会F的场。ACode#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;intmain(){ ios::sync_with_stdio(false); cin.tie(0); intt; cin>>t; while(t--){ inta,b; cin>>a>>b; intf=0; if(a%2==0&&am......
  • Codeforces Round 924 (Div. 2)
    CodeforcesRound924(Div.2)A-RectangleCutting解题思路:初始矩形长宽为\((a,b)\),如果我们切\(a\),那么一定不能再拼接\(a\),否则一定一样。所以我们拼接\(b\),即将\(a\)对半分开得到两个\((\frac{a}{2},b)\)矩形拼接。此时,如果\(\frac{a}{2}=b\)那么拼接出来的矩形和初......
  • Codeforces Round 905 (Div. 3)
    题目链接A.先算距离,特判0的位置,最后加4#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){strings;cin>>s;s=""+s;intlast=1,now,ans=0;for(inti=1;i<s.si......
  • Educational Codeforces Round 135 (Rated for Div. 2)C. Digital Logarithm(思维)
    目录题目链接题意题解代码题目链接C.DigitalLogarithm题意给两个长度位\(n\)的数组\(a\)、\(b\),一个操作\(f\)定义操作\(f\)为,\(a[i]=f(a[i])=a[i]\)的位数求最少多少次操作可以使\(a、b\)两个数组变得完全相同题解性质:对于任何数,经过两次操作我们一定可以让其变为\(......
  • CodeForces 1286C2 Madhouse (Hard version)
    洛谷传送门CF传送门可以把限制看成\(0.75n^2\)。发现\(0.75n^2=0.5n^2+2\times0.5(\frac{n}{2})^2\)。这启发我们询问一次\([1,n]\)和两次长度为\(\frac{n}{2}\)的区间。不妨问\([1,n],[1,\frac{n}{2}],[1,\frac{n}{2}+1]\)试试。注意到把\([1,\frac......
  • Educational Codeforces Round 145 (Rated for Div. 2)C. Sum on Subarrays(构造)
    很意思的一道构造题题意:给一个\(n、k\),让构造长度为n的数组满足,子数组为整数的个数为k个,负数的为\(k-(n+1)*n/2\),每个数的范围为\([-1000,1000]\)这种构造题可以考虑就是前一段可以一直用一样的、最小的。我们观察可以发现\(k+k-(n+1)*n/2=(n+1)*n/2\)也就是所有子数组......
  • CodeForces 1927G Paint Charges
    洛谷传送门CF传送门看到\(n\le100\)考虑\(O(\text{poly}(n))\)dp。发现从左向右决策,因为一个点可以向左或向右覆盖,所以需要记最靠左的未覆盖的位置\(j\)和最靠右的已覆盖位置\(k\),状态就是\(f_{i,j,k}\),dp最小的覆盖次数。转移的讨论很简单。考虑不覆盖还是向左......
  • Codeforces Round 919 (Div. 2)
    https://codeforces.com/contest/1920B还行,C、Egood(E据说是很典的dp但我是dp苦手),D、F1无聊,F2不会A.SatisfyingConstraints*800有\(n\)个条件,每个条件形如\(x\gek,x\lek\)或\(x\neqk\),\(k\)为整数。问满足条件的整数\(x\)的个数。先处理\(\ge,\le\),得到限制......