首页 > ACM题库 > HDU-杭电 > HDU 3024-Repairman-线段树-[解题报告]HOJ
2014
02-27

HDU 3024-Repairman-线段树-[解题报告]HOJ

Repairman

问题描述 :

The traveling repairman problem (TRP) is classical NP-Hard problem, which is also known as minimum latency problem (MLP) and delivery man problem. Suppose that we have a graph with n nodes, in each one there is a machine that has to be repaired, and there is only one repairman. We are given the time required by the repairman to travel among nodes. The objective is to find a tour that minimizes the total waiting time of all the machines. (ignore time of repairing)

Now for simplicity, we place all nodes on a straight line. Your task is to find out smallest sum of waiting time of all the machines.

输入:

The first line of input contains a single integer T, which is the number of test case. Each case starts with a line containing a single integer N (1 ≤ N ≤ 400), the number of nodes. The next line gives a list of N corrdinate of nodes. Each corrdinate is a integer in the range [-1000, 1000]. Consecutive integers are separated by a single space charcter. The repairman will depart from origin. Suppose he travels at unit speed.

输出:

The first line of input contains a single integer T, which is the number of test case. Each case starts with a line containing a single integer N (1 ≤ N ≤ 400), the number of nodes. The next line gives a list of N corrdinate of nodes. Each corrdinate is a integer in the range [-1000, 1000]. Consecutive integers are separated by a single space charcter. The repairman will depart from origin. Suppose he travels at unit speed.

样例输入:

2
2
-1 2
3
-1 1 2

样例输出:

5
8


#include <iostream>
#include <algorithm>
#define M 100005
using namespace std;

struct P {
    int left, right, lmax, rmax, smax, sum;
} tree[M << 2];

struct point {
    int x, y, v, d, pos, id;
} p[M];

void build(int left, int right, int now) {
    tree[now].lmax = tree[now].rmax = tree[now].smax = tree[now].sum = 0;
    tree[now].left = left;
    tree[now].right = right;
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        build(left, mid, now * 2);
        build(mid, right, now * 2 + 1);
    }
}

void insert(int pos, int val, int now) {
    if (tree[now].right – tree[now].left == 1) {
        tree[now].lmax = tree[now].rmax = tree[now].smax = tree[now].sum = val;
        return;
    }
    int mid = (tree[now].right + tree[now].left) / 2;
    int l = now * 2;
    int r = l + 1;
    if (pos < mid)
        insert(pos, val, l);
    else
        insert(pos, val, r);
    tree[now].sum = tree[l].sum + tree[r].sum;
    tree[now].lmax = max(tree[l].lmax, tree[l].sum + tree[r].lmax);
    tree[now].rmax = max(tree[r].rmax, tree[r].sum + tree[l].rmax);
    tree[now].smax = max(max(max(max(tree[now].lmax, tree[now].rmax)
            , tree[l].rmax + tree[r].lmax), tree[l].smax), tree[r].smax);


}

bool cmp(point a, point b) {
    return a.d < b.d;
}

bool rcmp(point a, point b) {
    return a.id < b.id;
}
int val[M];
int n, m;

int main() {
    while (scanf(“%d”, &n) == 1) {
        memset(val, 0, sizeof (val));
        for (int i = 0; i < n; i++) {
            scanf(“%d%d%d”, &p[i].x, &p[i].y, &p[i].v);
            p[i].d = p[i].x * p[i].x + p[i].y * p[i].y;
            p[i].id = i;
        }
        sort(p, p + n, cmp);
        int pos = 0;
        p[0].pos = 0;
        val[0] = p[0].v;
        for (int i = 1; i < n; i++) {
            if (p[i].d != p[i - 1].d) pos++;
            p[i].pos = pos;
            val[pos] += p[i].v;
        }
        build(0, pos + 1, 1);
        for (int i = 0; i <= pos; i++)
            insert(i, val[i], 1);
        sort(p, p + n, rcmp);
        scanf(“%d”, &m);
        while (m–) {
            char op;
            scanf(” %c”, &op);
            if (op == ‘Q’) {
                printf(“%d\n”, tree[1].smax);
                continue;
            } else {
                int id, x;
                scanf(“%d%d”, &id, &x);
                insert(p[id - 1].pos, x – p[id - 1].v + val[p[id - 1].pos], 1);
                val[p[id - 1].pos] += x – p[id - 1].v;
                p[id - 1].v = x;
            }
        }
    }
    return 0;
}

参考:http://zhulinb123.blog.163.com/blog/static/184414043201172203137897/


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }