POJ1083

题目LINK

题意解释

题意是从一个房子到另一个房子搬桌子，题意中两个搬桌子的进程中，如果两者在使用走廊的过程中没有重叠的部分那么就可以同时进行。这道题整体的思路是imos算法，就是想象一个轴，轴里有1 2 3 ... n，然后找出每次移动桌子的区间，在用类似俄罗斯方块的方法叠加上去，这道题的最终结果是叠加后最厚区间的高度。（建议自行百度1mos算法，十分直观）

收获

首先这道题的坑有两个。

1.给出的起始点可能小于终点 2.区间算的时候，一定是奇数到偶数，才能做到真正的区间全覆盖

代码技巧

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