题目链接：
首先要注意，对门的两个房间不能同时移桌子。我们读入房间号时，要对房间号做处理（比如令房间号=（房间号-1）/2），使得对门的两个房间的编号相同，方便处理。
其次，本题我给出两种解法。
解法一的思想是，将一次从from->to的移动看成一个线段，n次移动可以看成n条线段。将这n条线段画在数轴上，则最少需要移动的次数，等于线段重叠（两条线段至少包含相同的一点算作重合）的最大层数。这种解法似乎没有包含典型的贪心思想，至少我的愚见是这样。这种解法可以用数学归纳法证明。
解法二的思想是，先对所有移动(from->to)按from由小到大的顺序排序，然后每次按from从前往后取移动（这里的移动是指移动一张桌子），直到取不出来，算一次移动（这里的移动指移动若干张桌子）。这种解法更像贪心，但是我无法证明这种解法的正确性。如果哪位知道如何证明，请赐教。
解法一。
#include#include using namespace std;const int LEN = 200;int overlapCount[LEN];int main (){ int caseNum; scanf("%d",&caseNum); for (int i = 1;i <= caseNum;i ++) { int moveNum; scanf("%d",&moveNum); memset(overlapCount, 0, sizeof(overlapCount)); for (int j = 1;j <= moveNum;j ++) { int from, to; scanf("%d%d",&from,&to); from = (from - 1) / 2; to = (to - 1) / 2; if (from > to) swap(from, to); for (int k = from;k <= to;k ++) overlapCount[k] ++; } int max = 0; for (int j = 0;j < LEN;j ++) max = max > overlapCount[j] ? max : overlapCount[j]; printf("%d\n", max * 10); } return 0;}
解法二。
#include#include #include using namespace std;class Move{public: int from, to; int isMoved;};vector moves,onceMoveRec;//onceMoveRec记录一次移动中的所有移动计划int judgeAllMoved(int moveNum){ for (int i = 0;i < moveNum;i ++) if (moves[i].isMoved == 0) return 0; return 1;}int judgeCanMove(Move aMove){ //front是from小的move Move front,back; for (int i = 0;i < onceMoveRec.size();i ++) { if (onceMoveRec[i].from <= aMove.from) { front = onceMoveRec[i]; back = aMove; } else { back = onceMoveRec[i]; front = aMove; } if (back.from <= front.to) return 0; } return 1;}int cmp(const Move &m1, const Move &m2){ return m1.from < m2.from;}int main (){ int caseNum; scanf("%d",&caseNum); for (int i = 1;i <= caseNum;i ++) { moves.clear(); int moveNum; scanf("%d",&moveNum); Move aMove; //读入所有桌子的移动计划 for (int j = 1;j <= moveNum;j ++) { scanf("%d%d",&aMove.from,&aMove.to); aMove.from = (aMove.from - 1) / 2; aMove.to = (aMove.to - 1) / 2; if (aMove.from > aMove.to) swap(aMove.from,aMove.to); aMove.isMoved = 0; moves.push_back(aMove); } //按to从前往后排序。不排序是错的，我也不知道为什么 sort(moves.begin(),moves.end(),cmp); int moveCount = 0; int isAllMoved = 1; //如果没有移完 while ( ! judgeAllMoved(moveNum)) { onceMoveRec.clear(); for (int i = 0;i < moveNum;i ++) { if (moves[i].isMoved == 1) continue; if (judgeCanMove(moves[i])) { onceMoveRec.push_back(moves[i]); moves[i].isMoved = 1; } } moveCount ++; } printf("%d\n",moveCount * 10); } return 0;}