usaco2018 feb cu Hoofball

usaco2018 feb cu Hoofball

​​ In preparation for the upcoming hoofball tournament, Farmer John is drilling his N

N cows (conveniently numbered 1…N

1…N , where 1≤N≤100

1≤N≤100 ) in passing the ball. The cows are all standing along a very long line on one side of the barn, with cow i

i standing xi

xi units away from the barn (1≤xi≤1000

1≤xi≤1000 ). Each cow is standing at a distinct location.At the beginning of the drill, Farmer John will pass several balls to different cows. When cow i

i receives a ball, either from Farmer John or from another cow, she will pass the ball to the cow nearest her (and if multiple cows are the same distance from her, she will pass the ball to the cow farthest to the left among these). So that all cows get at least a little bit of practice passing, Farmer John wants to make sure that every cow will hold a ball at least once. Help him figure out the minimum number of balls he needs to distribute initially to ensure this can happen, assuming he hands the balls to an appropriate initial set of cows.

INPUT FORMAT (file hoofball.in):

The first line of input contains N

N . The second line contains N

N space-separated integers, where the i

i th integer is xi

xi .

OUTPUT FORMAT (file hoofball.out):

Please output the minimum number of balls Farmer John must initially pass to the cows, so that every cow can hold a ball at least once.

SAMPLE INPUT:

5 7 1 3 11 4 SAMPLE OUTPUT:

2 In the above example, Farmer John should pass a ball to the cow at x=1

x=1 and pass a ball to the cow at x=11

x=11 . The cow at x=1

x=1 will pass her ball to the cow at x=3

x=3 , after which this ball will oscillate between the cow at x=3

x=3 and the cow at x=4

x=4 . The cow at x=11

x=11 will pass her ball to the cow at x=7

x=7 , who will pass the ball to the cow at x=4

x=4 , after which this ball will also cycle between the cow at x=3

x=3 and the cow at x=4

x=4 . In this way, all cows will be passed a ball at least once (possibly by Farmer John, possibly by another cow).

It can be seen that there is no single cow to whom Farmer John could initially pass a ball so that every cow would eventually be passed a ball.

Problem credits: Dhruv Rohatgi

每次传球都是往最近的地方传球 中文题意出问题了.. 如果相同距离 则向最左边传球

那么首先一遍dfs判断哪些只有一个入度 那么给他一个球 然后再dfs一下 看一下环的情况 给每个环一个 球 即可

#include#include#include#include#define N 1100using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}struct node{ int y,next;}data[N];bool visit[N];int n,x[N],h[N],num,ans,in[N];inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num;}inline void dfs(int x){ visit[x]=1; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (!visit[y]) dfs(y); }}int main(){ freopen("hoofball.in","r",stdin); freopen("hoofball.out","w",stdout); n=read();for (int i=1;i<=n;++i) x[i]=read(); if (n==1) {puts("1");return 0;} sort(x+1,x+n+1);x[0]=x[n+1]=-10000; for (int i=1;i<=n;++i){ if (abs(x[i]-x[i-1])<=abs(x[i]-x[i+1])) insert1(i,i-1),in[i-1]++;else insert1(i,i+1),in[i+1]++; }for (int i=1;i<=n;++i) if (!in[i])dfs(i),++ans;int ans1=0; for (int i=1;i<=n;++i) if (!visit[i]) ++ans1; //if (ans1&1) return 1; printf("%d",ans+ans1/2); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。