首页 > ACM题库 > HDU-杭电 > HDU 3262-Seat taking up is tough-模拟-[解题报告]HOJ
2014
03-13

HDU 3262-Seat taking up is tough-模拟-[解题报告]HOJ

Seat taking up is tough

问题描述 :

Students often have problems taking up seats. When two students want the same seat, a quarrel will probably begin.
Zombies VS Plants

It will have very bad effect when such subjects occur on the BBS.
So, we urgently need a seat-taking-up rule. After several days of argument, the rule finally comes out:
As shown in the figure below, the seats in a classroom form a n×m grid( n rows and m columns), and every cell in the grid represents a seat. The coordinates of the seat in the north-west corner are (1,1) and the coordinates of the seat in the south-east corner seat are (n,m). As you know, some seats make you feel good and some seats don’t. So every seat has a “feeling index”.
Zombies VS Plants

Students can take up seats for himself and his friends. Of course, if a seat is already taken up by a student, it can’t be taken up by others.
For the convenience of communication between friends, when a student is trying to take up seats, he wants all the seats he needs to be consecutive and in the same row. If he can do that, he takes up all the seats he needs, and save the most western one for himself. For example, if a student wants to take up 3 seats, then taking (2,2),(2,3),(2,4) and saving (2,2) for himself is ok; but taking (2,2),(2,4),(2,5) is invalid because those seats are not consecutive. Under the precondition of accomplishing his seat-taking job, a student always wants the “feeling index” of his seat to be as large as possible.
However, if a student cannot take up all the seats he needs, he will just try to take up only one seat for himself because he doesn’t want to get into the trouble of explaining “Why they can get seats but I can’t?” to some of his friends. Of course he still wants the “feeling index” of his seat to be as large as possible in that situation.
Everyone wants to know where are the seats he can take up .This problem seems a little bit complicated for them. So they want you to write a program to solve the problem.

输入:

There are several test cases and the input ended by a line of “0 0 0”.
For each test case:
The first line contains three integers: n , m and k ( 1 <= n,m<=30, 1<=k<=50). It means that there are n rows of seats in the classroom and there are m seats in every row. k is the number of students who come into the classroom trying to take up seats.
Following are n lines describing the seats by north to south order .Each line represents a row of seats and contains m integers, indicating the “feeling index” of every seat in that row, by west to east order. “Feeling index” can be fit in a 32-bit integer.
Then k lines follow (We call them k “student lines”). Each line is in the format of “hh:mm q” ( 0 <= hh < 24, 0 <=mm <= 59, 1<=q<=50 ) meaning that a student comes into the classroom at mm minutes past hh o’clock, trying to take up q seats. mm and hh are all two digit integers with possible leading zero, and q is also an integer. Please note that when a student enters the class room, he begins to do his seat taking job immediately and the job takes no time.
It is guaranteed that the “feeling index” of every seat is different and no students come into the classroom at the same time.

输出:

There are several test cases and the input ended by a line of “0 0 0”.
For each test case:
The first line contains three integers: n , m and k ( 1 <= n,m<=30, 1<=k<=50). It means that there are n rows of seats in the classroom and there are m seats in every row. k is the number of students who come into the classroom trying to take up seats.
Following are n lines describing the seats by north to south order .Each line represents a row of seats and contains m integers, indicating the “feeling index” of every seat in that row, by west to east order. “Feeling index” can be fit in a 32-bit integer.
Then k lines follow (We call them k “student lines”). Each line is in the format of “hh:mm q” ( 0 <= hh < 24, 0 <=mm <= 59, 1<=q<=50 ) meaning that a student comes into the classroom at mm minutes past hh o’clock, trying to take up q seats. mm and hh are all two digit integers with possible leading zero, and q is also an integer. Please note that when a student enters the class room, he begins to do his seat taking job immediately and the job takes no time.
It is guaranteed that the “feeling index” of every seat is different and no students come into the classroom at the same time.

样例输入:

5 5 8
11 12 15 14 13
21 22 25 24 23
16 17 20 19 18
6 7 10 8 9
1 2 5 4 3
09:00 2  
09:01 5  
09:02 5  
09:03 5  
09:04 5  
09:05 3  
09:06 2  
09:07 3  
0 0 0

样例输出:

2 3
3 1
1 1
4 1
5 1
2 5
2 1
-1

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=3262

题意:教室有n*m个座位,每个座位有一个舒适值,有K个学生在不同时间段进来,要占t个座位,必须是连续的并且自己坐在最左边,如果有多个的话,找最舒适的座位,如果没有连续t个,那么只给自己找个最舒适的位子,如果都满的话,输出-1.

题解:一个简单的搜索模拟,注意的是,要排序每个同学进来的时间,而且输出要按照给的顺序输出,被坑了几次,样例数据太弱了。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s)  scanf("%s",s)
#define pi1(a)    printf("%d\n",a)
#define pi2(a,b)  printf("%d %d\n",a,b)
#define mset(a,b)   memset(a,b,sizeof(a))
#define forb(i,a,b)   for(int i=a;i<b;i++)
#define ford(i,a,b)   for(int i=a;i<=b;i++)

typedef long long LL;
const int N=33;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-8;

int n,m,k;
int xh[N][N];

struct xkn
{
    int time,ren;
    int i;
}p[55];

struct jilu
{
    int x,y;
}o[55];

bool cmp(xkn a,xkn b)
{
    return a.time<b.time;
}

bool yes(int i,int j,int ren)
{
    for(int k=0;k<ren;k++)
        if(xh[i][j+k]==-1)
            return false;
    return true;
}

void xiaohao(int ren,int t)
{
    int flag1=-1,flag2=-1;
    int Max1,Max2;
    int x,y;
    for(int i=0;i<n;i++)
        for(int j=0;j<=m-ren;j++)
        {
            if(yes(i,j,ren))
            {
                if(flag1==-1)
                {
                    flag1=1;
                    Max1=xh[i][j];
                    x=i;    y=j;
                }
                else if(Max1<xh[i][j])
                {
                    Max1=xh[i][j];
                    x=i;    y=j;
                }
            }
        }
    if(flag1!=-1)
    {
        //pi2(x+1,y+1);
        o[t].x=x+1; o[t].y=y+1;
        for(int k=0;k<ren;k++)
            xh[x][y+k]=-1;
        return ;
    }

    forb(i,0,n)
        forb(j,0,m)
        {
            if(xh[i][j]!=-1)
            {
                if(flag2==-1)
                {
                    flag2=1;
                    Max2=xh[i][j];
                    x=i;    y=j;
                }
                else if(Max2<xh[i][j])
                {
                    Max2=xh[i][j];
                    x=i;    y=j;
                }
            }
        }
    if(flag2!=-1)
    {
        //pi2(x+1,y+1);
        o[t].x=x+1; o[t].y=y+1;
        xh[x][y]=-1;
        return ;
    }
    o[t].x=-1; o[t].y=-1;
}

int main()
{
//    freopen("input.txt","r",stdin);
    while(scanf("%d%d%d",&n,&m,&k)&&(n+m+k))
    {
        forb(i,0,n) forb(j,0,m) si1(xh[i][j]);
        forb(i,0,k)
        {
            int a,b;
            scanf("%d:%d %d",&a,&b,&p[i].ren);
            p[i].time=a*60+b;
            p[i].i=i;
        }
        sort(p,p+k,cmp);
        forb(i,0,k)
        {
            xiaohao(p[i].ren,p[i].i);
        }
        forb(i,0,k)//必须按照开始的顺序输出
        {
            if(o[i].x==-1)
                puts("-1");
            else
                pi2(o[i].x,o[i].y);
        }
    }
    return 0;
}

参考:http://blog.csdn.net/xh_reventon/article/details/12205035


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }