Life of xhu

一些吐槽 & HOJ_1511 & HOJ_1513

Apr 08, 2014  |  吐槽  |  HOJ  |  Algorithm

你对Python和Ruby都了解一点啊,那你以后就来我们公司做前端吧。

我不知道这句话的因果关系是怎么得出来的。

Java也就能Android开发,Web这块基本没人用。

阿里表示不服。

其实Java也是一门脚本语言。

呵呵。

~~我是萌萌的昏割线~~~

1511:水题一道,根据给出的时间和路程,求速度,如果没完成比赛,则输出-,注意一下格式即可。

改吗如下:

#include <iostream>
#include <cstdio>
#include <string>
#include <iomanip>
using namespace std;

int calc(string s){
    return (s[0] - '0') * 3600 + ((s[2] - '0') * 10 + s[3] - '0') * 60 + (s[5] - '0') * 10 + s[6] - '0';
}

int main(){
    int n, team, ans, sum;
    bool flag;
    double d;
    string input;
    cin >> n >> d;
    while(scanf("%d", &team)!=EOF){
        flag = false;
        sum = 0;
        for(int i = 0; i < n; i++){
            cin >> input;
            if(input[0] == '-')
                flag = true;
            if(flag)
                continue;
            sum += calc(input);
        }    
        cout << fixed << setw(3) << team << ": ";
        if(flag)
            cout << '-' << endl;
        else{
            ans= (int)((double)sum / d + 0.5);
            cout << ans / 60 << ':';
            if(ans % 60 >= 10)
                cout << ans % 60 << " min/km" << endl;
            else
                cout << '0' << ans % 60 << " min/km" << endl;
        }    
    }    
}

1513:题意大致是这样的,用括号给出一个树的描述,构建这棵树后,每次寻找值最小的叶节点,去掉这个叶节点以及与其相邻的边,然后输出边的另一端,一直循环,直到树里只剩最后一个节点,输出这个节点的值。

建树的过程很简单,使用就行了,关键在于叶节点的选取,需要注意的是,题目里的树是unrooted tree,也就是说,任何只与一条边相连的节点都可以看作是叶节点,这也能解释为什么第二个例子中首先去掉的是节点1

我的思路是,使用一个数组node[60]存储节点,下标对应的值是一个节点连接的边数,另一个二维数组edge[200][2]存储边的情况,然后对node数组进行node_num - 1次的遍历:

  1. 找出node中值为1的最小的下标,然后将其对应值减1;
  2. 遍历edge数组,在所有未被使用的边中寻找一端等于刚刚得到的下标的边,并将边的另一端节点在node中对应值减1;
  3. 将2中使用的边标记为已使用,并重复1。

代码如下:

#include <iostream>
#include <string>
#include <memory>
using namespace std;

typedef struct Stack{
    int data[60], top;
}Stack;

int main(){
    int node[60], num, edge_num, node_num, init, tmp;
    int edge [200][2];
    bool used[200];
    string input;
    Stack s;
    while(getline(cin, input)){
        s.top = edge_num = node_num = 0;
        memset(node, 0, sizeof(node));
        memset(used, false, sizeof(used));
        for(int i = 0; i < input.length(); i++){
            if('0' <= input[i] && input[i] <= '9'){
                if('0' <= input[i + 1] && input[i + 1] <= '9'){
                    num = (input[i] - '0') * 10 + input[i + 1] - '0';
                    i++;
                }
                else
                    num = input[i] - '0';
                if(s.top != 0){
                    edge[edge_num][0] = s.data[s.top - 1];
                    edge[edge_num++][1] = num;
                    node[s.data[s.top - 1]]++;
                    node[num]++;
                }
                node_num++;
                s.data[s.top++] = num;
            }else if(input[i] == ')')
                s.top--;
        }
        for(int i = 0; i < node_num - 1; i++){
            init = 0;
            for(int j = 0; j < 60; j++){
                if(node[j] == 1){
                    if(!init)
                        init = j;
                    else if(j < init)
                        init = j;
                }
            }
            node[init]--;
            for(int j = 0; j < edge_num; j++){
                if(!used[j]){
                    if(edge[j][0] == init){
                        tmp = edge[j][1];
                        node[edge[j][1]]--;
                        used[j] = true;
                        break;
                    }else if(edge[j][1] == init){
                        tmp = edge[j][0];
                        node[edge[j][0]]--;
                        used[j] = true;
                        break;
                    }
                }
            }
            if(!i)
                cout << tmp;
            else
                cout << ' ' << tmp;
        }
        cout << endl;
    }
}

Copyright © 2018 - xhu - Powered by Gin,jQuery,Animate.css,Semantic UI