2 条题解
-
0
#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
#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
- 上传者