2012级第一次训练题解

POJ 1003 Hangover

题意: 求n使得1/2+1/3+...+1/n>=x.

#include <stdio.h>
int main()
{
    double x,ans;
    int i;
    while(scanf("%lf",&x) && x>0)
    {
        ans=0.0;
        for(i=2;ans<x;i++) ans+=1.0/i;
        printf("%d card(s)\n",i-2);
    }
    return 0;
}

 

POJ 1004 Financial Management

题意: 求12个浮点数的平均值.

#include <stdio.h>
int main()
{
    double ans=0.0,x;
    int i;
    for(i=0;i<12;i++)
    {
        scanf("%lf",&x);
        ans+=x;
    }
    printf("$%.2lf\n",ans/12);
    return 0;
}

 

POJ 1005 I Think I Need a Houseboat

题意: 如图,一个海岸线从原点开始以半圆形扩展,每年50平方英里的速度.给你一个点(x,y),求出覆盖到该点的时间.

思路: 求出经过点(x,y)的半圆形的面积,除以50然后向上取整就是最终结果.不过此题的数据不是特别强,所以对结果向下取整再加1也对.

#include <stdio.h>
#include <math.h>
#define PI 3.1415926
int main()
{
    int T,ncase=0,ans;
    double x,y,r;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lf%lf",&x,&y);
        r=sqrt(x*x+y*y);
        ans=(int)ceil(PI*r*r/2/50);
        printf("Property %d: This property will begin eroding in year %d.\n",++ncase,ans);
    }
    printf("END OF OUTPUT.\n");
    return 0;
}

 

POJ 1007 DNA Sorting

题意: 给出m个长度都为n的DNA字符串,按照每个字符串的逆序数从小到大排序(如果逆序数相同则按照给出的顺序输出).

思路: 这一题主要是考察稳定排序(排序后关键字相同的元素按照原来的顺序排列).可以直接使用比较简单的冒泡排序,选择排序,也可以使用效率较高的快速排序(C语言库函数中的qsort()).

但是qsort()是不稳定的排序,可以通过增加一个下标使之成为稳定排序.

#include <stdio.h>
#include <stdlib.h>
typedef struct{
    char s[52];
    int x,id;
}dna;
dna a[102];
int cal(char s[])
{
    int i,j,ans=0;
    for(i=0;s[i];i++)
        for(j=0;j<i;j++) if(s[i]<s[j])
            ans++;
    return ans;
}
int cmp(const void *a,const void *b)
{
    dna aa=*(dna *)a;
    dna bb=*(dna *)b;
    if(aa.x!=bb.x) return aa.x-bb.x;
    return aa.id-bb.id;
}
int main()
{
    int n,m,i;
    scanf("%d%d",&m,&n);
    for(i=0;i<n;i++)
    {
        scanf("%s",a[i].s);
        a[i].x=cal(a[i].s);
        a[i].id=i;
    }
    qsort(a,n,sizeof(a[0]),cmp);
    for(i=0;i<n;i++) printf("%s\n",a[i].s);
    return 0;
}