HDU 1050(搬椅子数学)

题意是在一个有 400 个房间的走廊中搬动房间里的椅子，如果两次的路线重叠，就要分两次搬动，如果不重叠，就可以一次搬动。

开始的时候直接当成求线段重叠条数的题，发现这种思路完全是错的，比如 1 - 3，2 - 4，3 - 5 这一组，只需搬动两次即可，但找重叠线段的话就会找到 3 条重叠线段。

然后打算直接模拟做，加入一点贪心的思路，用结构体数组存搬动要求，按椅子搬动的距离从小到大排序，扫描一边整个结构体数组，将搬动的路径标记，

若已经标记过，则 ++ans，注意 ans 的初值为 1，因为第一次搬动要算作一次搬动，但这一次没有与任何路径重叠。

模拟做的直接超时了......

代码如下：

 1 int t,n,ans,mp[405];
 2 bool f;
 3 struct node
 4 {
 5     int from,to,len;
 6 }p[205];
 7 bool cmp(node a,node b)
 8 {
 9     return a.len!=b.len?a.len<b.len:a.from<b.from;
10 }
11 int main()
12 {
13     scanf("%d",&t);
14     while(t--)
15     {
16         scanf("%d",&n);
17         ans = 1;
18         memset(mp,0,sizeof(mp));
19         for(int i = 0; i < n; ++i)
20         {
21             scanf("%d%d",&p[i].from,&p[i].to);
22             p[i].len = p[i].to-p[i].from;
23         }
24         sort(p,p+n,cmp);
25         for(int i = 0; i < n; ++i)
26         {
27             f = true;
28             for(int j = p[i].from; j <= p[i].to; ++j)
29             {
30                 if(mp[j])
31                 {
32                     ans++;
33                     fill(mp+p[i].from,mp+p[i].to,-1);
34                     f = false;
35                     break;
36                 }
37             }
38             if(f) fill(mp+p[i].from,mp+p[i].to,-1);
39         }
40         printf("%d
",ans*10);
41     }
42     return 0;
43 }

View Code

看了其他人的做法，才知道不应该把房间看作排列在一条线段上的点，而是如题目中描述的那样排在一对平行线上：

这样将房间前的位置用一个长 200 的一维数组来存，在每次的路径的每一个位置上增加 1，这个数组中的最大值即为搬动次数。如图示的情况即为：1，2，2，0，...

搬动次数即为 2 次。

代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5      int t,n,from,to,ans;
 6      int cnt[204],tmp;
 7      scanf("%d",&t);
 8      while(t--)
 9      {
10         scanf("%d",&n);
11         memset(cnt,0,sizeof(cnt));
12         ans = 0;
13         for(int i = 1; i <= n; ++i)
14         {
15             scanf("%d%d",&from,&to);
16             if(from > to)
17             {
18                 tmp = from;
19                 from = to;
20                 to = tmp;
21             }
22             for(int j = (from+1)/2; j <= (to+1)/2; ++j)
23                 cnt[j]++;
24         }
25         for(int i = 1; i <= 201; ++i)
26             if(ans<cnt[i]) ans = cnt[i];
27         printf("%d
",ans*10);
28      }
29      return 0;
30 }

View Code

另外还知道了一点，在交换两变量的值时，用位运算的方法更快：

如 temp = a; a = b; b = temp;

用位运算实现：a = a^b; b = a^b; a = a^b;

本题中由于没注意到有可能搬动是从房间号较大的房间搬向房间号较小的房间，还 wa 了......

解决办法就是再加一步如果是这种情况就交换两房间的号码，即还是从小到大的顺序，这里直接交换的结果是 15ms，用位运算交换的结果是 0ms.

以后就要改用这种位运算交换的方法了。

特向这篇博客的作者致谢：https://www.cnblogs.com/cchun/archive/2011/05/14/2520076.html

HDU 1050(搬椅子 数学)

HDU 1050(搬椅子数学)