2014
02-27

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;
}

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;
}

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;
}