首页 > ACM题库 > 九度OJ > 九度-1159-坠落的蚂蚁[解题代码]
2013
12-13

九度-1159-坠落的蚂蚁[解题代码]

题目来源:2011年北京大学计算机研究生机试真题

题目描述:

    一根长度为1米的木棒上有若干只蚂蚁在爬动。它们的速度为每秒一厘米或静止不动,方向只有两种,向左或者向右。如果两只蚂蚁碰头,则它们立即交换速度并继续爬动。三只蚂蚁碰头,则两边的蚂蚁交换速度,中间的蚂蚁仍然静止。如果它们爬到了木棒的边缘(0或100厘米处)则会从木棒上坠落下去。在某一时刻蚂蚁的位置各不相同且均在整数厘米处(即1,2,3,…99厘米),有且只有一只蚂蚁A速度为0,其他蚂蚁均在向左或向右爬动。给出该时刻木棒上的所有蚂蚁位置和初始速度,找出蚂蚁A从此时刻到坠落所需要的时间。

输入:

    第一行包含一个整数表示蚂蚁的个数N(2<=N<=99),之后共有N行,每一行描述一只蚂蚁的初始状态。每个初始状态由两个整数组成,中间用空格隔开,第一个数字表示初始位置厘米数P(1<=P<=99),第二个数字表示初始方向,-1表示向左,1表示向右,0表示静止。

输出:

    蚂蚁A从开始到坠落的时间。若不会坠落,输出“Cannot fall!”

样例输入:
4
10 1
90 0
95 -1
98 -1
样例输出:
98

cpp 代码如下:
#include <stdio.h>
#include <stdlib.h>
struct aa{
        int pos;
        int sd;
};
aa a[100];
aa b[100];
int cmp(const void *a,const void *b)
{
        struct aa *ap = (struct aa*)a;
        struct aa *bp = (struct aa*)b;
        return (*ap).pos-(*bp).pos;
}
int main()
{
        int n;
        while(scanf("%d",&n)!=EOF){
                int i,j=0,k=0,lf = 0,rf = 0,af = 0;
                for(i=0;i<n;i++)
                {
                        scanf("%d %d",&a[i].pos,&a[i].sd);
                }
                qsort(a,n,sizeof(struct aa),cmp);
                for(i=0;i<n;i++){
                        if( !j && a[i].sd == 1 ) {b[k++] = a[i];lf++;}
                        if(  j && a[i].sd == -1 ) {b[k++] = a[i];rf++;}
                        if( a[i].sd == 0 ) {b[k++]=a[i];j=1;af=k-1;}
                }
                if( lf == rf ) printf("Cannot fall!\n");
                else if( lf > rf ){
                        printf("%d\n",100-b[af-1-rf].pos);
                }else if( lf < rf  ){
                        printf("%d\n",b[af+1+lf].pos);
                }
        }
        return 0;
}
/**************************************************************
	Problem: 1159
	User: coder
	Language: C++
	Result: Accepted
	Time:0 ms
	Memory:1024 kb
****************************************************************/


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  3. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  4. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。