社区讨论

求hack

P2170选学霸参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo3ipkrq
此快照首次捕获于
2023/10/24 07:17
2 年前
此快照最后确认于
2023/10/24 07:17
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define maxn 20002
using namespace std;
int n,m,k;
int dp,siz[maxn],dp1;
struct node{
    int fa[maxn];
    void init(){
        for(int i=1;i<=n;i++){
            fa[i]=i;
            siz[i]=1;
        }
    }
    int getfather(int x){
       return fa[x]==x?x:fa[x]=getfather(fa[x]); 
    }
    void hb(int x,int y){
        int fax=getfather(x);
        int fay=getfather(y);
        if(fax!=fay){
            if(siz[fax]>siz[fay]){
                swap(fax,fay);
            }
            fa[fax]=fay;
            siz[fay]+=siz[fax];
        }
    }
}bcj;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    bcj.init();
    for(int i=1;i<=k;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        bcj.hb(x,y);
    }
    for(int i=1;i<=n;i++){
        if(bcj.getfather(i)==i){
            if(abs(m-dp)>abs(m-dp-siz[i]))
            dp+=siz[i];
            //cout<<abs(m-dp[cnt-1])<<" "<<abs(m-dp[cnt-1]-siz[i])<<endl;
        }
    }
	for(int i=n;i>=0;i--){
        if(bcj.getfather(i)==i){
            if(abs(m-dp1)>abs(m-dp1-siz[i]))
            dp1=dp1+siz[i];
            //cout<<abs(m-dp[cnt-1])<<" "<<abs(m-dp[cnt-1]-siz[i])<<endl;
        }
    }
    if(abs(m-dp1)==abs(m-dp)){
		printf("%d",min(dp,dp1));
	}else if(abs(m-dp1)>abs(m-dp)){
		printf("%d",dp);
	}else printf("%d",dp1);
    return 0;
}
本题正解是dp,但是可以通过正向贪心选一遍,反向贪心选一遍来通过。
求是数据水了还是可以这样做。

回复

2 条回复,欢迎继续交流。

正在加载回复...