网站建设源代码怎么搭建,购物网站开发教程视频,网站改版 seo,wordpress播放网盘传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你1,2,...,n1,2,...,n1,2,...,n一共nnn个数#xff0c;你需要将其分成mmm组#xff0c;使得每组的中位数为bib_ibi#xff0c;保证bib_ibi互不相同。 中位数取ck12c_{\frac{k1}{2}}c2k1 n,m≤1…传送门
文章目录题意思路题意
给你1,2,...,n1,2,...,n1,2,...,n一共nnn个数你需要将其分成mmm组使得每组的中位数为bib_ibi保证bib_ibi互不相同。 中位数取ck12c_{\frac{k1}{2}}c2k1 n,m≤1e5n,m\le1e5n,m≤1e5
思路
考虑将中位数看作分割点那么这个序列就被分成了m1m1m1段我们发现每两段都可以各取一个数来抵消所以最后剩下的一定都在同一段里。 考虑最大段中包含的个数分两种情况讨论 (1)(1)(1)最大段中的个数≤\le≤其他各段之和此时可以将除了最大段的其他段相互抵消让后再让其与最大段抵消由于每次抵消只能减去偶数个所以最终一定只剩下了000个或111个如果剩了一个我们可以让最后一个剩下让后放在前面的某个后面即可。 (2)(2)(2)最大段的个数其他段之和此时抵消后剩余的数都在这个最大段内假设最大段之前有xxx个位置是要求的中位数那么如果x≥x\gex≥剩余的数的时候有解。 最后排个序判断一下即可。
// Problem: E - Median
// Contest: Virtual Judge - 2021多校第六场补题
// URL: https://vjudge.net/contest/451552#problem/E
// Memory Limit: 524 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int a[N];int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--) {scanf(%d%d,n,m);for(int i1;in;i) a[i]0;for(int i1;im;i) {int x; scanf(%d,x);a[x];}vectorPIIv;int cnt0;for(int i1;in;i) {int num0;while(in!a[i]) num,i;v.pb({num,cnt});cnt;}sort(v.begin(),v.end());int sum0;for(auto x:v) sumx.X;if(v.back().Xsum-v.back().Xv.back().Y) puts(YES);else puts(NO); }return 0;
}
/**/
