题目LINK
题意解释
题意是从一个房子到另一个房子搬桌子,题意中两个搬桌子的进程中,如果两者在使用走廊的过程中没有重叠的部分那么就可以同时进行。这道题整体的思路是imos算法,就是想象一个轴,轴里有1 2 3 ... n,然后找出每次移动桌子的区间,在用类似俄罗斯方块的方法叠加上去,这道题的最终结果是叠加后最厚区间的高度。(建议自行百度1mos算法,十分直观)
收获
首先这道题的坑有两个。
1.给出的起始点可能小于终点 2.区间算的时候,一定是奇数到偶数,才能做到真正的区间全覆盖
代码技巧
- max_element()这个在algorithm的头文件里,非常好用
AC代码
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef struct member{
int s;
int j;
}member;
member input[200];
void in(int total){
int i = 0;
while(total > 0){
scanf("%d %d",&input[i].s,&input[i].j);
if(input[i].s > input[i].j){
int tmp = input[i].s;
input[i].s = input[i].j;
input[i].j = tmp;
}
if(input[i].j%2 == 1)input[i].j++;//this is a trap
if(input[i].s%2 == 0)input[i].s--;//
total--;
i++;
}
}
void solve(int total){
int i = 0;
int table[400];
int cost = 0;
memset(table,0,sizeof(table));
while(i < total){
for(int j = input[i].s; j <= input[i].j; j ++){
table[j]++;
}
i++;
}
cout << *max_element(table,table + 400)*10 << endl;
}
int main()
{
int t,total;
scanf("%d\n",&t);
while(t > 0){
scanf("%d\n",&total);
in(total);
solve(total);
t--;
}
return 0;
}