首页 > 代码库 > BestCoder Round #2

BestCoder Round #2

2024-07-14 20:37:03   223人阅读

TIANKENG’s restaurant

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 600    Accepted Submission(s): 280


Problem Description
TIANKENG manages a restaurant after graduating from ZCMU, and tens of thousands of customers come to have meal because of its delicious dishes. Today n groups of customers come to enjoy their meal, and there are Xi persons in the ith group in sum. Assuming that each customer can own only one chair. Now we know the arriving time STi and departure time EDi of each group. Could you help TIANKENG calculate the minimum chairs he needs to prepare so that every customer can take a seat when arriving the restaurant?
 

Input
The first line contains a positive integer T(T<=100), standing for T test cases in all.

Each cases has a positive integer n(1<=n<=10000), which means n groups of customer. Then following n lines, each line there is a positive integer Xi(1<=Xi<=100), referring to the sum of the number of the ith group people, and the arriving time STi and departure time Edi(the time format is hh:mm, 0<=hh<24, 0<=mm<60), Given that the arriving time must be earlier than the departure time.

Pay attention that when a group of people arrive at the restaurant as soon as a group of people leaves from the restaurant, then the arriving group can be arranged to take their seats if the seats are enough.
 

Output
For each test case, output the minimum number of chair that TIANKENG needs to prepare.
 

Sample Input
2
2
6 08:00 09:00
5 08:59 09:59
2
6 08:00 09:00
5 09:00 10:00
 

Sample Output
11
6
 

Source
BestCoder Round #2
 

将时间离散化一下，然后将这个时间段里面的人数存到数组里面。
//640MS	296K
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<stack>
#include<queue>
#include<vector>

#pragma comment(linker, "/STACK:1024000000");
#define M 100007
#define inf 0x3f3f3f3f
#define ll long long
#define mod 1000000009
#define eps (1e-8)
using namespace std;
int ans[1500];
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
      memset(ans,0,sizeof(ans));
      int n,num,s_hour,s_minute,e_hour,e_minute,minn=inf,maxx=-1,count=-1;
      scanf("%d",&n);
      for(int i=0;i<n;i++)
      {
          scanf("%d %d:%d%d:%d",&num,&s_hour,&s_minute,&e_hour,&e_minute);
          int l=s_hour*60+s_minute;
          int r=e_hour*60+e_minute;
          if(l<minn)minn=l;
          if(r>maxx)maxx=r;
          for(int j=l;j<r;j++)
            ans[j]+=num;
      }
      for(int i=minn;i<=maxx;i++)
        if(ans[i]>count)count=ans[i];
      printf("%d\n",count);
   }
  return 0;
}

TIANKENG’s travel

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 409    Accepted Submission(s): 101


Problem Description
TIANKENG has get a driving license and one day he is so lucky to find a car. Every day he drives the car around the city. After a month TIANKENG finds that he has got high driving skills and he wants to drive home. Assuming that we regard the map of Hangzhou as a two-dimensional Cartesian coordinate system, the coordinate of the school is (sx, sy), the coordinate of TIANKENG’s home is (ex,ey). There are n gas stations distributing along the road and the coordinate of the ith gas station is (xi, yi). Because there is something wrong with the car engine, TIANKENG can drive the car for L miles after every time he fills up the gas. Assuming that TIANKENG must fill up the gas when he passes by a gas station and the initial status of the tank is full. TIANKENG must drive on the straight line and he can only choose to drive to school or home or gas station. Your task is to tell TIANKENG the minimum times he needs to charge fuel to go home successfully.
 

Input
The first line contains a positive integer T(T<=30), referring to T test cases.
For each test case, the first line contains two integers n(0<=n<=1000), L(1<=L<=100000), which mean n gas stations in all and the distance TIANKENG can drive with the full tank respectively. The second line contains two integers sx, sy, which refers to the coordinate of the school.
The third line contains two integers ex, ey, which refers to the coordinate of TIANKENG’s home.
Then following n lines, each line contains two integer xi, yi, which refers to the coordinate of gas station.

Assuming that all the coordinates are different! All the coordinates satisfied [0,1000000].
 

Output
For each test case, if TIANKENG cannot go home successfully, print “impossible”(without quotes), otherwise print the minimum times of charging fuel.
 

Sample Input
2
2 1000
0 0
2000 1000
1000 0
2000 0
0 1000
0 0
2000 1000
 

Sample Output
2
impossible
 

Source
BestCoder Round #2
 

明显的最短路，如果两个位置的距离小于l，那么建边，最后从起点跑一遍最短路。
可是题目要求如果经过一个加油站那么就必须在这个加油站加油，如果三个加油站在同一直线上，且两端的加油站距离小于l，如果按照上面建边，就会把中间的加油站忽略掉，显然不符合情况，因此两点之间还有其它点的也不能建边。判断三点是否一条直线，可以用叉积判断。
//171MS	4320K
#include<stdio.h>
#include<string.h>
#include<queue>
#include<algorithm>
#define M 1017
#define inf 0x3f3f3f3f
#define ll long long
#pragma comment(linker, "/STACK:1024000000");
using namespace std;
int t,n;
long long l;
int s,e,num=0;
int dist[M] ,vis[M] ,head[1001005];
struct sa
{
    int id;
    long long x,y;
}node[M] ;
struct E
{
    int v,next,cap;
}Edge[1001005];
void addEdge(int u,int v,int c)
{
    Edge[num].v=v;Edge[num].cap=c;
    Edge[num].next=head[u];
    head[u]=num++;
}
int cmp(sa a,sa b)
{
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}
long long judge(long long  a,long long b)
{
    long long x=(node[a] .x-node[b] .x)*(node[a] .x-node[b] .x);
    long long y=(node[a] .y-node[b] .y)*(node[a] .y-node[b] .y);
    long long len=l*l;
    return x+y;
}
void SPFA()                   //  源点为0，汇点为sink。
{
    queue<int>q;
    for(int i=0;i<n;i++)dist[i]=inf;
    q.push(s);
    dist[s] = 0;
    vis[s] =1;
    while(!q.empty())        //  这里最好用队列，有广搜的意思，堆栈像深搜。
    {
        int u =q.front();
        q.pop();vis[u]=0;
        for(int i=head[u]; i!=-1;i=Edge[i].next)
        {
            int v=Edge[i].v;
            if(dist[v]>dist[u]+1)
            {
                dist[v]=dist[u]+1;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=true;
                }
            }
        }
    }
}
bool cha(int i,int j,int k)
{
    int x1=node[i] .x-node[j] .x;
    int x2=node[j] .x-node[k] .x;
    int y1=node[i] .y-node[j] .y;
    int y2=node[j] .y-node[k] .y;
    if(x1*y2-x2*y1)return true;
    return false;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(head,-1,sizeof(head));
        num=0;
        scanf("%d%I64d",&n,&l);
        n+=2;
       for(int i=0;i<n;i++)
        {
            scanf("%d%d",&node[i] .x,&node[i] .y);
            node[i] .id=i;
        }
        sort(node,node+n,cmp);
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                if(judge(i,j)<=l*l)
                {
                    int flag=1;
                    for(int k=i+1;k<j;k++)
                        if(!cha(i,j,k)){flag=0;break;}
                    if(flag){addEdge(i,j,1);addEdge(j,i,1);}
                }
        for(int i=0;i<n;i++)
        {
            if(node[i].id==0)s=i;
            if(node[i].id==1)e=i;
        }
        SPFA();
        if(dist[e] ==inf)printf("impossible\n");
        else printf("%d\n",dist[e] -1);
    }
    return 0;
}



联系
我们