poj3190 Stall Reservations解题报告

链接:poj3190

Stall Reservations
**Time Limit:** 1000MS **Memory Limit:** 65536K
**Total Submissions:** 4735 **Accepted:** 1688 Special Judge

Description

Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.

Help FJ by determining:

  • The minimum number of stalls required in the barn so that each cow can have her private milking period
  • An assignment of cows to these stalls over time

Many answers are correct for each test dataset; a program will grade your answer.

Input

Line 1: A single integer, N

Lines 2..N+1: Line i+1 describes cow i’s milking interval with two space-separated integers.

Output

Line 1: The minimum number of stalls the barn must have.

Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.

Sample Input

5

1 10

2 4

3 6

5 8

4 7

Sample Output

4

1

2

3

2

4

Hint

Explanation of the sample:

Here’s a graphical schedule for this output:

Time     1  2  3  4  5  6  7  8  9 10


Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>


Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..


Stall 3 .. .. c3>>>>>>>>> .. .. .. ..


Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

Other outputs using the same number of stalls are possible.

大意就是有多个牛要挤奶,但是每个牛都特别犟,只在自己的时间内产奶,且不与其他牛共享stall,可以添加任意个stall,求最小的stall数且输出每个牛隶属的stall..
各种坑....不多说,对时间限制相当严格,直接贪心于是就直接爆时间了,

其实还是对堆的应用不熟练啊,

正确思路应该是首先建立一个结构体存储每个牛的产奶时间的左右端点,然后按照产奶开始时间从小到大排序,优先处理先开始产奶的奶牛,同时结构体内还需要一个变量记录每个牛的id,以便排序之后的处理和输出:

struct Cow
{
    int l,r,co;
}c[maxn];
bool cmp(Cow c1,Cow c2){
    if(c1.l==c2.l)return c1.r<c2.r;
    else return c1.l<c2.l;
}

然后,建立一个表示stall的优先队列,这个优先队列每次先取出队列中最早结束的奶牛结构体Cow,

比如现在优先队列中有m头奶牛,对第m+1头奶牛,如果这头奶牛的开始时间小于等于优先队列中最早结束产奶的奶牛的结束时间,那么就需要增加一个stall,于是将这头奶牛加入优先队列;如果这头奶牛的开始时间大于上述时间,那么取出优先队列的top,并将这头奶牛加入队列,同时维护一个ans值和ansl数组以便输出.

对优先队列,应该首先对结构体的<运算符进行重载:

bool operator <(const Cow& a,const Cow& b) 
{
    if(a.r==b.r)return a.l>b.l;
    else return a.r>b.r;
}

下面是完整AC代码:

/*
* Filename:    poj3190d.cpp
* Desciption:  我要疯了,真的
* Created:     2016年03月11日 14时16分29秒 星期五
* Author:      JIngwei Xu [mail:xu_jingwei@outlook.com]
*
*/
#include<bitset>
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<queue>
#define INT_MAX 1<<30
using namespace std;
typedef long long ll;
const int INF=0x7F;
int n;
const int maxn=50000+7;
int anl[maxn];
struct Cow
{
    int l,r,co;
}c[maxn];
bool cmp(Cow c1,Cow c2){
    if(c1.l==c2.l)return c1.r<c2.r;
    else return c1.l<c2.l;
}
bool operator <(const Cow& a,const Cow& b) 
{
    if(a.r==b.r)return a.l>b.l;
    else return a.r>b.r;
}
Cow c1;
priority_queue<Cow> pq;
int sel=1,ans=1;
void solve(){
    pq.push(c[0]);
    anl[c[0].co]=ans;
    for (int i = 1; i < n; i += 1)
    {
        c1=pq.top();
        if (c[i].l>c1.r)
        {
            anl[c[i].co]=anl[c1.co];
            pq.pop();
            pq.push(c[i]);
        }else{
            ans++;
            anl[c[i].co]=ans;
            pq.push(c[i]);
        }
    }
    printf("%d\n",ans);
    for (int i = 0; i < n; i += 1)
    {
        printf("%d\n",anl[i]);
    }
}

int main()
{
//ios_base::sync_with_stdio(0);
#ifdef JIngwei_Xu
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
#endif
    while (scanf("%d",&n)!=EOF)
    {
        for (int i = 0; i < n; i += 1)
        {
            scanf("%d%d",&c[i].l,&c[i].r);
            c[i].co=i;
//            pq.push(c[i]);
        }
        sort(c,c+n,cmp);
//        for (int i = 0; i < n; i += 1)
//        {
//            cout<<c[i].co<<":"<<c[i].l<<","<<c[i].r<<endl;
//        }
//        while (!pq.empty())
//        {
//            cout<<pq.top().co<<":"<<pq.top().l<<","<<pq.top().r<<endl;
//            pq.pop();
//        }
        solve();
    }
    return 0;
}

 


文章作者: crazyX
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 crazyX !
评论
 上一篇
ubuntu 15.04配置蓝牙以使用蓝牙耳机 ubuntu 15.04配置蓝牙以使用蓝牙耳机
折腾很久了,终于搞定了. 应该也适用于其他内核版本相差不大的ubuntu版本,哦对了,是针对双系统下的ubuntu. 首先,终端下输入 lsusb 查看自己的蓝牙设备id,我的是 Bus 001 Device 004: ID 04ca:20
2016-03-12
下一篇 
ubuntu 简单安全配置 ubuntu 简单安全配置
1.安装sudo apt-get install ufw 2.启用sudo ufw enablesudo ufw default deny运行以上两条命令后,开启了防火墙,并在系统启动时自动开启。关闭所有外部对本机的访问,但本机访问外部正常
2016-03-10
  目录