POJ3190

最新推荐文章于 2021-03-31 13:35:36 发布

algzjh

最新推荐文章于 2021-03-31 13:35:36 发布

阅读量408

点赞数

分类专栏： # 模拟与贪心文章标签：优先队列贪心区间

本文链接：https://blog.csdn.net/algzjh/article/details/53148003

版权

模拟与贪心专栏收录该内容

54 篇文章

订阅专栏

本文介绍了一种解决奶牛挤奶时间安排问题的高效算法。通过使用优先队列来最小化所需的挤奶隔间数量，并确保每头奶牛都能在指定的时间段内单独挤奶。文章提供了一个具体的例子和完整的C++实现代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Stall Reservations

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 5822		Accepted: 2130		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

Sample Output

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.

Source

USACO 2006 February Silver

抽象一下就是：有几个区间，不相交的区间可以放在一个隔间里，

要使隔间数最少，求每个区间所在的隔间号~

使用优先队列

#include<cstdio>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;

struct node
{
    int x,y,c;
    friend bool operator<(node a,node b)
    {
        return a.y>b.y;//y从小到大
    }
}p[50005];

bool cmp(node a,node b)
{
    return a.x<b.x;
}

int t[50005];

int main()
{
    int i,j,n;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d%d",&p[i].x,&p[i].y);
        p[i].c=i;
    }
    int r=0;
    sort(p,p+n,cmp);
    priority_queue<node> q;
    q.push(p[0]);
    t[p[0].c]=++r;
    for(i=1;i<n;i++)
    {
        node g=q.top();
        if(g.y<p[i].x)
        {
            t[p[i].c]=t[g.c];
            q.pop();
            q.push(p[i]);
        }
        else
        {
            t[p[i].c]=++r;
            q.push(p[i]);
        }
    }
    printf("%d\n",r);
    for(int i=0;i<n;i++)
        printf("%d\n",t[i]);
    return 0;
}