Codeforces Round #727 (Div. 2) Stable Groups

这里应该写什么

很显然,先把所有学生排序并且分组

然后,把两个组合并

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
int n,m,k,x;
int a[2000001];
int fa[2000001];
int cnt;
int co[3000001]; 
int find(int x){
    return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
} 
signed main(){
    scanf("%lld%lld%lld",&n,&k,&x);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+n+1);
    for(int i=2;i<=n;++i){
        if(a[i]-a[i-1]<=x){
            fa[i]=i-1;
        }else{
            fa[i]=i;
        }
    }
    fa[1]=1;
    for(int i=2;i<=n;++i){
        if(find(fa[i])!=find(fa[i-1])){
            cnt++;
            co[cnt]=(a[i]-a[i-1]-x)/x+(((a[i]-a[i-1])%x)!=0);   
        } 
    }
    cnt++;
    int tem=cnt;
    sort(co+1,co+cnt);
    for(int i=1;i<cnt;++i){
    //  cout<<co[i]<<endl;
        if(k>=co[i]){
            tem--;
            k-=co[i];
        }else
        break;
    }
    cout<<tem;
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇