USACO 2018 February Contest, Bronze Hoofball

本文主要是介绍USACO 2018 February Contest, Bronze Hoofball，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 Hoofball

时间限制: 1 Sec   内存限制: 128 MB
提交: 166   解决: 27
[ 提交][ 状态][ 讨论版][命题人: admin]

题目描述

输入

输出

样例输入

5

7 1 3 11 4

样例输出

2

提示

来源

【题意】

    扑朔迷离的英文题； 不， 是扑朔迷离的英语水平， 看不懂题意；；；；；；

    是这样的， 某个点传球， 传两边，  传给距离最小的， 其次，当距离相等时 传给左边；

    问最少需要几个球 让所有的人都曾经摸过球。

【思路】 

    想着类似于 波浪线这种， 有上升有下降， 取顶点，  对于 平台  取奇数的 ，  但是实现起来特别麻烦。

    用 环标记，   把 某个数 存左边还是右边  建立 关系，  构成 几个环， 然后DFS 搜一下环，

    最后 没有标记的点，就属于平台部分了，  然后/2  加上环的个数

【代码实现】

/*
* Date: 4/3/2018
* Tile: UPC 补题
* Category: DFS
* AU: siz
* WA: 1
* Attation: 标记后， 进行DFS 搜索，，最后扫描， 平台的情况
*/
#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+5;using namespace std;int head[MAXN],vis[MAXN];
int in[MAXN];
int cot,n,m;
struct node{int v,next;
}edge[MAXN];
void init()
{cot=0;memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));
}
void add(int u,int v)
{edge[++cot].next=head[u];edge[cot].v=v;head[u]=cot;
}
void dfs(int s)
{vis[s]=1;for(int i=head[s];i!=-1;i=edge[i].next){int v=edge[i].v;if(!vis[v])dfs(v);}
}int a[MAXN];
int main()
{int ans1=0,ans2=0;cin>>n;init();for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1);a[0]=a[n+1]=-INF;if(n==1){cout<<1<<endl;return 0;}for(int i=1;i<=n;i++){if(abs(a[i]-a[i-1]) <= abs(a[i]-a[i+1]))add(i,i-1),in[i-1]++;elseadd(i,i+1),in[i+1]++;}for(int i=1;i<=n;i++){if(!in[i]){dfs(i);ans1++;}}for(int i=1;i<=n;i++)if(!vis[i])ans2++;cout<<ans1+(ans2/2)<<endl;return 0;
}

这篇关于USACO 2018 February Contest, Bronze Hoofball的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---