[原创]POJ 3190 解题报告

2015-12-18 21:16:40 Tabris_ 阅读数：451

博客爬取于2020-06-14 22:45:17
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50354268

http://poj.org/problem?id=3190

题目大意： 每一只奶牛都要在区间[a,b]的时段内独自享受一个牛栏 如果两只牛的时间岔开了
那很好 它们两个用一个牛栏就好了  如果不能岔开  那么只好分别用一个牛栏了

这题主要是贪心的思想  寻找最优解  但是单单贪心是不够的  你需要记录每只牛在第几只牛栏
而且你要判断这些牛那些能在一起而那些不能在一起   所以本题  用到了优先队列  优先级就为最小的结束时间
然后进行比较  这里就看代码的注释就好了
其实思路还是比较好像 但是操作起来着实不宜  再加上博主平时就不怎么用队列 更不用说优先队列的  所以本题迟迟不能写出来啊 所以粘了大神的代码

大神的代码 虽然看懂了 但是自己写的话很多地方都不能很好的处理   还是技术不行啊

1
2
3
4
5
6
#include<queue>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
struct node
{
    int x,y;
    int no;
    int ss;
    friend bool operator< (node n1, node n2)//定义优先级
    {
        return n1.y > n2.y;
    }
} p[50050];
bool cmp1 (node a,node b)//排序 贪心用的
{
    if (a.x==a.y) return a.y<b.y;
    else return a.x<b.x;
}
bool cmp2 (node a,node b)//排序 为输出格式准备的  按次序输出牛在第几栏
{
    return a.ss<b.ss;
}
int main()
{
    int n,i,tag=0,co=0;
    scanf ("%d",&n);
    for (i=0; i<n; i++)
    {
        scanf ("%d%d",&p[i].x,&p[i].y);
        p[i].ss=i;//标记次序
    }
    sort (p,p+n,cmp1);
    tag=p[0].x;//表示最小的右边界
    priority_queue <node> que;//优先队列 优先级为右值
//  for (i=0;i<n;i++)         //测试用 就是看下排序
//      printf ("%d:%d %d\n",i,p[i].x,p[i].y);
    for (i=0; i<n; i++)//核心代码了
    {
        if (tag>=p[i].x)  //如果不能与之前的牛放到同一栏
        {
            co++;    //那就单独放一栏里
            p[i].no=co;//表示第几只牛在第几个栏
            que.push(p[i]);
            tag=que.top().y;  //更新右边界  队头是优先队列里右边界做小的
        }
        else
        {
            p[i].no=que.top().no;  //可以与之前的牛放到一起  所以栏数相同
            que.pop();
            que.push(p[i]);
            tag=que.top().y;
        }
    }
//    while (!que.empty())
//    {
//        printf ("%d ",que.top().y);
//        que.pop();
//    }
    printf ("%d\n",co);  //总栏数
    sort (p,p+n,cmp2);    //排序二排序  未达成输出顺序
    for (i=0; i<n; i++)
        printf("%d\n",p[i].no);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<queue>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct node {
    int l,r;
    int no;
    int id;
    friend bool operator<(node a,node b){
        return a.r>b.r;
    }
}a[50050];

bool cmp1(node a,node b){
    if(a.l==a.r) return a.r<b.r;
    return a.l<b.l;
}
bool cmp2(node a,node b){
    return a.id<b.id;
}

int main(){
    int n,tag,cnt= 0;;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].id=i;
    }
    sort(a,a+n,cmp1);
    tag=a[0].l;
    priority_queue<node >que;
    for(int i=0;i<n;i++){
        if(tag>=a[i].l){
            a[i].no=++cnt;
            que.push(a[i]);
        }
        else {
            a[i].no=que.top().no;
            que.pop();
            que.push(a[i]);
        }
        tag=que.top().r;
    }
    printf("%d\n",cnt);
    sort(a,a+n,cmp2);
    for(int i=0;i<n;i++){
        printf("%d\n",a[i].no);
    }
    return 0;
}