poj3347

题意：给予n个正方形，要求45°角放置，最左边的正方形紧贴Y轴，所有的正方形的下面的端点都在X轴上。然后按照正方形不能交错但要尽可能的挨着的原则，摆放，最后输出从上往下看能看到的正方形的编号。

方法：看了各种Discuss和解题报告，发现有个人的思路很不错，但他是将坐标纸缩小√2，这样并不能避免小数，其实扩大√2倍就能避免小数了。办法是，每新增一个正方形，就让他与左侧的每一个正方形贴紧，求的其左端坐标，最终结果一定是最大的那个。然后求的相应的最右端坐标。这样就转化为了线段，最后用朴素的n2算法求出每条线段没有被覆盖的长度，如果长度大于0，即可输出

WA点：移位运算符>>优先级比+低，故a = b + c << 1等价于 a = （(b + c) << 1）;另外，乘以2是移一位，不是两位！

代码：

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

using namespace std;

struct Segment

{

int left,right,len;

};

Segment seg[50];

int main()

{

int n;

while(cin >> n,n)

{

for(int i = 0; i < n; i++)

{

cin >> seg[i].len;

seg[i].left = 0;

for(int j = 0; j < i; j++)

{

seg[i].left = max(seg[i].left,seg[j].right - abs(seg[i].len - seg[j].len));

}

seg[i].right = seg[i].left + seg[i].len * 2;

}

for(int i = 1; i < n; i++)

{

for(int j = 0; j < i; j++)

{

if(seg[i].left < seg[i].right)

{

if(seg[i].len > seg[j].len && seg[i].left < seg[j].right)

seg[j].right = seg[i].left;

else if(seg[i].len < seg[j].len && seg[i].left < seg[j].right)

seg[i].left = seg[j].right;

}

}

}

for(int i = 0; i < n; i++)

{

if(seg[i].left < seg[i].right)

cout << i + 1 << " ";

}

cout << endl;

}

return 0;

}