2 条题解

  • 0
    @ 2025-10-8 17:15:00
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=500005;
    int n,a[maxn],Du[maxn],ans,cnt,nxt[maxn];
    bool vis[maxn];
    
    void DFS(int x){
    	if(vis[x])return;
    	vis[x]=1;DFS(nxt[x]);
    }
    int main(){
    	scanf("%d", &n);
    	for(int i=1;i<=n;i++)scanf("%d", &a[i]);
    	sort(a+1,a+n+1);
    	for(int i=1;i<=n;i++){
    		if(i==1)Du[i+1]++,nxt[i]=i+1;
    		else if(i==n)Du[i-1]++,nxt[i]=i-1;
    		else{
    			if(a[i]-a[i-1] <= a[i+1]-a[i])Du[i-1]++,nxt[i]=i-1;
    			else Du[i+1]++,nxt[i]=i+1;
    		}
    	}
    	for(int i=1;i<=n;i++)if(!Du[i])ans++,DFS(i);
    	for(int i=1;i<=n;i++)if(!vis[i])cnt++;
    	printf("%d",ans+cnt/2);
    	return 0;
    }
    
    • 0
      @ 2025-10-8 17:14:50
      #include<bits/stdc++.h>
      using namespace std;
      const int maxn=500005;
      int n,a[maxn],Du[maxn],ans,cnt,nxt[maxn];
      bool vis[maxn];
      
      void DFS(int x){
      	if(vis[x])return;
      	vis[x]=1;DFS(nxt[x]);
      }
      int main(){
      	scanf("%d",&n);
      	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
      	sort(a+1,a+n+1);
      	for(int i=1;i<=n;i++){
      		if(i==1)Du[i+1]++,nxt[i]=i+1;
      		else if(i==n)Du[i-1]++,nxt[i]=i-1;
      		else{
      			if(a[i]-a[i-1]<=a[i+1]-a[i])Du[i-1]++,nxt[i]=i-1;
      			else Du[i+1]++,nxt[i]=i+1;
      		}
      	}
      	for(int i=1;i<=n;i++)if(!Du[i])ans++,DFS(i);
      	for(int i=1;i<=n;i++)if(!vis[i])cnt++;
      	printf("%d",ans+cnt/2);
      	return 0;
      }
      • 1

      信息

      ID
      7845
      时间
      1000ms
      内存
      256MiB
      难度
      8
      标签
      递交数
      143
      已通过
      21
      上传者