Moving Tables
程序员文章站
2022-03-26 11:37:40
...
题意:在一个狭窄的走廊里将桌子从一个房间移动到另一个房间,走廊的宽度只能允许一个桌子通过。给出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;
}
下一篇: 我成了她表妹的备胎
推荐阅读
-
mysql server is running with the --skip-grant-tables option
-
create table,show tables,describe table,DROP TABLE,ALTER TABLE ,怎么使用?
-
MySQL open_tables和opened_tables
-
How to Create Responsive Tables using CSS without