澳门威利斯人_威利斯人娱乐「手机版」

来自 网络资讯 2019-11-16 06:11 的文章
当前位置: 澳门威利斯人 > 网络资讯 > 正文

POJ_2376_Cleaning Shifts(贪心)

POJ_2376_Cleaning Shifts(贪心)

Cleaning Shifts

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 12788   Accepted: 3312

Description

Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.

Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.

Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.

Input

* Line 1: Two space-separated integers: N and T

* Lines 2..N 1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.

Output

* Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.

Sample Input

3 10
1 7
3 6
6 10

Sample Output

2

Hint

This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.

INPUT DETAILS:

There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.

OUTPUT DETAILS:

By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.

题意:农夫有N头牛。今后他想让某个牛去做家务活。然后她把意气风发天分成T个时间点,也正是一天的时间点是间距[1,T]。他想要任何一个小时点都有牛在做家务活。未来交付每头牛的劳作时间,问您是或不是用起码的牛满意他的必要,即用起码的日子段覆盖掉这一天([1,T])。借使不可能满意则输出-1,不然输出最少的牛数量。

分析:贪心题。标题意思很明确是求起码的间隔覆盖掉大跨距。先对这么些时刻段排好序(见代码),这些排序应该是没什么难点的。然后呢,第三只牛确定要选,就从那头牛以前,选取下三只牛。下一只牛怎么取舍呢?即在满足条件的牛里面(注意:满意条件的牛是若是开头工时start>=cow[0].y 1 就可以卡塔尔国,接收右侧界值最大的十一分,因为这样子能够覆盖掉最多的时刻段。就那样类推,故贪心法求之。

代码项目清单:

#include

#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int maxn = 25000 5; const int maxd = 1000000 5; struct Edge{ int x; int y; }cow[maxn]; int N,T; int X,Y; bool cmp(Edge a,Edge b){ if(a.x==b.x) return a.y>b.y; return a.xmaxy){ maxy=cow[End].y; } } if(maxy!=Start){ ans ; Start=maxy; } else{ if(End==N-1){ //已覆盖掉区间 break; } else{ //表明中间有个别时间点覆盖不到 printf("-1n"); return ; } } } printf("%dn",ans); return ; } int main(){ input(); solve(); return 0; }

Shifts(贪心) Cleaning Shifts Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 12788 Accepted: 3312 Description Farmer John is assigning some of his N...

poj 2376 Cleaning Shifts,poj2376

                                                                                             Cleaning Shifts

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 18151   Accepted: 4620

Description

Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T. 

Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval. 

Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.

Input

* Line 1: Two space-separated integers: N and T 

* Lines 2..N 1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.

Output

* Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.

Sample Input

3 10
1 7
3 6
6 10

Sample Output

2

Hint

This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed. 

INPUT DETAILS: 

There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10. 

OUTPUT DETAILS: 

By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows.

Source

USACO 二零零二 December Silver         贪心算法 题解:给定T个时辰间隔,区间范围[1,T],差异牛有例外的行事时间,求起码不怎么头牛职业能够覆盖这么些区间。        首先以牛伊始职业的光阴前后相继顺序排序,之后持续循环更新起源=终点 1,在始发工时能隐讳起源的牛中,每趟选出四头工时最晚的牛,更新终点        具体AC代码:

#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
using namespace std;
const int N_max = 25000;
pair<int, int>cows[N_max];
int N, T;
bool cmp(const pair<int, int>&a, const pair<int, int>&b) {
    return (a.first<b.first||(a.first==b.first&&a.second>b.second));
}
int solve() {
    int used_cows = 0;
    int end = 0, num = 0;
    while (end < T) {
        int begin = end   1;//此时的end是上一头牛的工作结束时间,此时的begin为当前的牛工作开始时间要在begin之前
        for (int i = num;i < N;i  ) {//选出新的一头牛,使得工作结束时间越晚越好
            if (cows[i].first <= begin) {
                if (cows[i].second >= begin)//别忘加等于,有可能牛的工作区间只有1个,譬如3-3
                    end = max(end, cows[i].second);//在能选的牛中选一条,使得工作的时间到最晚

            }
            else {
                num=i;//没有符合要求的牛可以挑选了,换新牛
                break;
            }
        }
        //判断这选出来的牛是否符合要求,即它的工作结束时间必须要大于begin,否则之间有区间不能被覆盖
        if (begin > end) {//此时begin是大于等于当前挑选出来的牛的开始时间,而end是当前牛的工作结束时间
            return -1;
        }
        else used_cows  ;
    }
    return used_cows;
}
int main() {
    scanf("%d%d", &N, &T);
        for (int i = 0;i < N;i  )
        scanf("%d%d", &cows[i].first, &cows[i].second);
        sort(cows, cows   N,cmp);
        cout << solve() << endl;
    return 0;
}

 

2376 Cleaning Shifts,poj2376 Cleaning Shifts Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 18151 Accepted: 4620 Description Farmer John is assigning some of his...

本文由澳门威利斯人发布于网络资讯,转载请注明出处:POJ_2376_Cleaning Shifts(贪心)

关键词: 澳门威利斯人