hdu 刷题记录

1007 最近点对问题，采用分治法策略搞定

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 using namespace std;
 5 int n;
 6 struct node
 7 {
 8   double x;
 9   double y;
10 }p[100005];
11 int a[100005];
12 double cmpx(node a,node b)
13 {
14   return a.x<b.x;
15 }
16 double cmpy(int a,int b)
17 {
18   return p[a].y<p[b].y;
19 }
20 double min(double a,double b)
21 {
22   return a<b?a:b;
23 }
24 double dis(node a,node b)
25 {
26   return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
27 }
28 double find(int l,int r)
29 {
30      if(r==l+1)
31       return dis(p[l],p[r]);
32      if(l+2==r)
33       return min(dis(p[l],p[r]),min(dis(p[l],p[l+1]),dis(p[l+1],p[r])));
34      int mid=(l+r)>>1;
35      double ans=min(find(l,mid),find(mid+1,r));
36      int i,j,cnt=0;
37      for(i=l;i<=r;i++)
38      {
39        if(p[i].x>=p[mid].x-ans&&p[i].x<=p[mid].x+ans)
40           a[cnt++]=i;
41      }
42      sort(a,a+cnt,cmpy);
43      for(i=0;i<cnt;i++)
44      {
45        for(j=i+1;j<cnt;j++)
46        {
47          if(p[a[j]].y-p[a[i]].y>=ans) break;
48          ans=min(ans,dis(p[a[i]],p[a[j]]));
49        }
50      } 
51      return ans;
52 }
53 int main()
54 {
55     int i;
56    
57     while(scanf("%d",&n)!=EOF)
58     {
59       if(!n) break;
60       for(i=0;i<n;i++)
61        scanf("%lf %lf",&p[i].x,&p[i].y);
62       sort(p,p+n,cmpx);
63       printf("%.2lf%
",find(0,n-1)/2);
64     }
65     return 0;
66 }

View Code

1008 沙茶题，水题预警

 1  #include<stdio.h>
 2 int main()
 3 {
 4     int n;
 5     int start,a;
 6     int t;
 7     int i;
 8     while(scanf("%d",&n),n)
 9     {
10         t=0;start=0;
11         for(int i=1;i<=n;i++)
12         {
13             scanf("%d",&a);
14             if(a>start)t+=6*(a-start);
15             else t+=4*(start-a);
16             t+=5;
17             start=a;
18         }
19         printf("%d
",t);
20     }    
21     return 0; 
22 }

View Code

1009 贪心排序乱搞一波

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 #include<ctype.h>
 5 #include<algorithm>
 6 #include<stack>
 7 #include<queue>
 8 #include<set>
 9 #include<math.h>
10 #include<vector>
11 #include<map>
12 #include<deque>
13 #include<list>
14 using namespace std;
15 typedef struct node{
16     int j;
17     int f;
18     double d;
19 }MC;
20 MC a[1003];
21 bool cmp(MC a,MC b)
22 {
23     return a.d>b.d;
24 }
25 int main()
26 {
27     int n,m,i;
28     double t;
29     while(cin>>n>>m)
30     {
31         if(n==-1&&m==-1)
32             break;
33         for(int i=0;i<m;i++)
34         {
35             cin>>a[i].j>>a[i].f;
36             a[i].d=1.0*a[i].j/a[i].f;
37         }
38         sort(a,a+m,cmp);
39         t=0;
40         for(int i=0;i<m;i++)
41         {
42             if(n>a[i].f)
43             {
44                 t+=a[i].j;
45                 n-=a[i].f;
46             }
47             else
48             {
49                 t+=n*a[i].d;break;
50             }
51         }
52         printf("%.3lf
",t);
53     }
54     return 0;
55 }

View Code

2710 机智的离线打表

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 #include<ctype.h>
 5 #include<algorithm>
 6 #include<stack>
 7 #include<queue>
 8 #include<set>
 9 #include<math.h>
10 #include<vector>
11 #include<map>
12 #include<deque>
13 #include<list>
14 using namespace std;
15 int a[20010]={0,1};
16 int main()
17 {
18     for(int i=2;i<=20000;i++)
19     {
20         if(a[i]==0)
21         {
22             for(int j=i;j<=20000;j+=i)
23                 a[j]=i;
24         }
25     }
26     int n;
27     while(scanf("%d",&n)!=EOF)
28     {
29         int ans;
30         int maxn=0;
31         while(n--)
32         {
33             int m;
34             scanf("%d",&m);
35             if(a[m]>maxn)
36             {
37                 ans=m;
38                 maxn=a[m];
39             }
40         }
41         printf("%d
",ans);
42     }
43     return 0;
44 }

View Code