洛谷P3458 [POI2007]SKA-Rock Garden
? 解题记录 ? ? 洛谷 ?    2018-06-09 21:40:14    628    0    0


题目描述

Vicomte de Bajteaux is the owner of a renowned collection of boulders. Up to now, he has kept it in thecellars of his palace, but recently, he has decided to display the collection in his vast gardens.

The gardens have a shape of rectangle, whose sides are 1\ 000\ 000\ 0001 000 000 000 units long and are parallel to east-westand north-south geographical directions. For each boulder, vicomte has determined coordinates ofthe point, which he would like it to be placed in (the coordinates are simply distances to the southern and western side of the garden), and gave them to his servants. Unfortunately he has forgot to tell them the orderof the coordinates (i.e. for some of the boulders the first coordinate of a point is the so called " yy coordinate",i.e. the ordinate, while for others the so called " xx coordinate", i.e. the abscissa).

The servants, unaware of thisfact, have placed the boulders assuming customary coordinate ordering (as in standard Cartesian coordinates:

the abscissa, commonly known as " xx coordinate", first).

To protect his collection, vicomte has decided to surround it with a fence. For aesthetic reasons thefence has to be a rectangle, with sides parallel to the sides of the garden. The garden layout has been planned, so that the total length of the fence be minimal (i.e. in the space of all coordinate orderings, the original ordering of vicomte requires the minimal length of the fence - we assume that the rectangle may have sides of zero length).

The servants have to move the boulders so that the length of the fence required is minimal lest their mistake become obvious. Each boulder may only be moved in a way that preserves the coordinate set: by interchanging its coordinates. As the boulders are heavy, the servants would like to minimize their effort, by minimizing the weight of the boulders to be moved.

Task

Write a programme which:

reads the present positions of the boulders in the gardens and their respective weights, determines a sequence of moves, which minimizes the length of the fence required to protect the boulders and also minimizes the weight of the boulders to be moved, writes the outcome to the standard output.

Blue Mary是一个有名的石头收藏家。迄今为止,他把他的藏品全部放在他的宫殿的地窖中。现在,他想将他的藏品陈列在他的花园中。皇家花园是一个边长为1000000000单位的平行于坐标轴的正方形。对于每个石头,Blue Mary都有一个他想放置的坐标,然后将他告诉他的属下。不幸的是,他忘了告诉他们坐标的顺序(比如无法分辨(x,y)和(y,x))。属下们,就自己决定了每个石头的具体位置。为了保护他的藏品,Blue Mary决定建造一个篱笆来保护他们。为了美学的需要,篱笆也被设计为平行于坐标轴的矩形。如果花园的布局知道了,那么就可以知道最短长度的篱笆的布局。他的属下们需要变换石头的坐标使得篱笆的长度最少。每个石头只能从(x,y)变换为(y,x),由于每个石头的重量不一样。属下们希望他们移动的石头的重量和最少。

输入输出格式

输入格式:

 

The first line of the standard input contains a single integer nn ( 2n1 000 000 ), denoting the number of boulders in the collection. The following nn lines contain three integers x_ixi , y_iyi and m_imi each ( 0xi,yi1 000 000 000 , 1m2000 ), separated by single spaces, denoting the present coordinates and the weight of ii 'th boulder. No unordered pair of coordinates will appear in the input more than once.

 

输出格式:

 

The first line of the standard output should contain two integers, separated by a single space - the minimal length of fence possible and the minimal weight of the boulders to be moved in order to obtain such a length.

The second line should contain a sequence of nn zeros and/or ones - ii 'th element of the sequence should be a one if in the optimal solution the i 'th boulder is to be moved and zero otherwise. Should more than one correct solutions exist, your programme is to write out any one of them.

 

输入输出样例

输入样例#1: 复制
5
2 3 400
1 4 100
2 2 655
3 4 100
5 3 277
输出样例#1: 复制
10 200
01010​​

 

 本题容易观察到把所有的石头移动到一边肯定是最优的,但是我刚开始以为只有两种情况就WA了,看了下题解才发现居然还有两种情况没考虑到?引用一张图:

(图片来自Wolfycz大佬的博客)

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 5, inf = 0x7fffffff;
int x[maxn], y[maxn], w[maxn];
int n, ans[4], mid, vis[4][maxn], mn[4][2] = {inf, inf, inf, inf, inf, inf, inf, inf};
int mx[4][2], id, mans = inf;

bool judge(int x, int y, int id) {
    swap(x, y);
    if(x < mn[id][0] || x > mx[id][0] || y < mn[id][1] || y > mx[id][1]) return false;
    return true;
}

int nx, ny;

int main() {
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &x[i], &y[i], &w[i]);
        nx = x[i], ny = y[i];
        if(nx > ny) swap(nx, ny);
        mn[0][0] = min(mn[0][0], nx);
        mx[0][0] = max(mx[0][0], nx);
        mn[0][1] = min(mn[0][1], ny);
        mx[0][1] = max(mx[0][1], ny);
        mn[1][0] = min(mn[1][0], ny);
        mx[1][0] = max(mx[1][0], ny);
        mn[1][1] = min(mn[1][1], nx);
        mx[1][1] = max(mx[1][1], nx);
    }
    mn[2][0] = mn[1][0], mn[2][1] = mn[1][1];
    mx[2][0] = mx[0][0], mx[2][1] = mx[0][1];
    mn[3][0] = mn[0][0], mn[3][1] = mn[0][1];
    mx[3][0] = mx[1][0], mx[3][1] = mx[1][1];
    for(register int j = 0; j < 4; ++j)
        for(register int i = 1; i <= n; ++i) {
            if(!judge(x[i], y[i], j)) 
                vis[j][i] = 1, ans[j] += w[i];
        }
    for(register int i = 0; i < 4; ++i) if(mans > ans[i]) mans = ans[i], id = i;
    printf("%lld %d\n", 2LL * (mx[id][0] - mn[id][0] + mx[id][1] - mn[id][1]), ans[id]);
    for(register int i = 1; i <= n; ++i) {
        putchar('0' + (vis[id][i]));
    }
    return 0;
}


上一篇: 洛谷P3514 [POI2011]LIZ-Lollipop

下一篇: 洛谷P3577 [POI2014]TUR-Tourism

628 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航