欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Moving Tables

程序员文章站 2022-03-26 11:37:40
...

Moving Tables
Moving Tables
Moving Tables

题意:在一个狭窄的走廊里将桌子从一个房间移动到另一个房间,走廊的宽度只能允许一个桌子通过。给出t,表示有t组测试数据。再给出n,表示要移动n个桌子。n下面有n行,每行两个数字,表示将桌子从a房间 移到b房间。走廊的分布图如一图所示,每移动一个桌子到达目的地房间需要花10分钟,问移动n个桌子 所需要的时间。

思路:若移动多个桌子时,所需要经过的走廊没有重合处,即可以同时移动。若有一段走廊有m个桌子都 要经过,一次只能经过一个桌子,则需要m*10的时间移动桌子。设一个数组,下标值即为房间号。桌子经过房间时,该房间号为下标对应的数组值即加10。最后找到最大的数组值,即为移动完桌子需要的最短时间。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <ctype.h>
#include <cstring>
#include <cstdio>
#include <set>
#include <sstream>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define MAXX 100005
#define SIS std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
//#include<bits/stdc++.h>
using namespace std;
//const int MAX =100;
const int mod=1e9+7;
/*const double PI=3.14159265359;
const double esp=1e-5;
//int mp[MAXX];
int  a[200005],b[100005],c[100005];
int n,m,d,x,cnt=0,k;
int num[10005];
int N,M,L;
struct node{
   int v,len,w;
   int next;
}E[2*10010];
int p[1010],eid;
void init()
{
    memset(p,-1,sizeof(p));
    eid=0;
}
void inser(int u,int v,int len)
{
    E[eid].v=v;
    E[eid].len=len;
    E[eid].next=p[u];
    p[u]=eid++;
}
int dis[1010];*/
//bool vis[1010];
ll pow_mod(ll a,ll b)
{
    ll res=1;
    while(b>0)
    {
        if(b&1)
        {
            res=res*a%mod;
        }
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
int n,m;
int a[410];
int ans;
int main(){
  SIS;
  int t;
  cin>>t;
  while(t--)
  {
      memset(a,0,sizeof(a));
      int s,e;
      cin>>n;
      while(n--)
      {
          cin>>s>>e;
          if(s>e)
            swap(s,e);
          if(s%2==0)
            s--;
          if(e%2!=0)
            e++;
          for(int i=s;i<=e;i++)
            a[i]+=10;

      }
      printf("%d\n",*max_element(a,a+405));//STL寻找区间最大
  }



    return 0;
}

相关标签: 技巧