Moving Tables

83 阅读 0 评论 55 点赞

我是靠谱客的博主务实果汁，这篇文章主要介绍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("%dn",*max_element(a,a+405));//STL寻找区间最大
  }

return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#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("%dn",*max_element(a,a+405));//STL寻找区间最大
  }



    return 0;
}