当前位置: 代码迷 >> 综合 >> POJ1083 水题
  详细解决方案

POJ1083 水题

热度:87   发布时间:2024-01-16 14:01:55.0

题意:

两排房间搬桌子但只要一个走廊,输入一组房间号,求最短搬完的时间

要点:

就是一个区间求交集的问题,输入的两个房间号作为前区间和后区间,有交集说明不能同时搬,交集最大值即为至少需要的时间。注意看图,前区间如果是偶数要-1,后区间如果为奇数要+1,例如:2,3实际对应的区间是1,4,看图可以知道这个区间内的走廊都不能用

ps:话说这道题分类是dp来着,感觉没有关系啊

代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <math.h>
using namespace std;
int a[500];int main()
{ int t;scanf("%d", &t);while (t--){memset(a, 0, sizeof(a));int i,n,x,y;scanf("%d", &n);for (i = 0; i < n; i++){scanf("%d%d", &x, &y);if (x > y)swap(x, y);//头文件是algorithmif (x % 2 == 0)x--;if (y % 2 == 1)y++;for (int j = x; j <= y; j++)a[j]++;//区间内的数组都+1,如果有交集就会一直加上去}int max = 0;for (i = 0; i < 500; i++)if (a[i]>max)max = a[i];printf("%d\n", max*10);}return 0;
}


  相关解决方案