ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1303. Минимальное покрытие

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
using namespace std;
#define N 900000
struct seq
{
    int l;
    int r;
};
seq se[N];
int m;
bool cmp(const seq &s1,const seq &s2)
{
    if(s1.l==s2.l)
        return s1.r>s2.r;
    return s1.l<s2.l;
}
int main()
{
    //while(scanf("%d",&m)!=EOF)
    //{
    scanf("%d",&m);
        int left,right;
        queue<int>que;
        while(!que.empty())que.pop();
        int i=0,j;
        while(scanf("%d%d",&left,&right))
        {
            if(left==0&&right==0)break;
            se[i].l=left;
            se[i].r=right;
            i++;
        }
        sort(se,se+i,cmp);
        int rightf=0;
        int maxlen=0;
        int num=0;
        int p=-1;
        int ff=0;
        for(j=0;j<i;j++)
        {

            if(se[j].l<=rightf&&se[j].r-rightf>maxlen)
            {
                maxlen=se[j].r-rightf;
                p=j;
            }
            else if(p!=-1&&maxlen>0)
            {
                que.push(p);
                rightf=rightf+maxlen;
                maxlen=0;
                num++;
                j=j-1;
            }
            if(rightf>=m)
            {
                ff=1;
                break;
            }
        }
        if(maxlen>0)
        {

            rightf=rightf+maxlen;
            maxlen=0;
            num++;
            if(rightf>=m)
            {
                que.push(p);
                ff=1;
            }
        }
        if(ff)
        {
            printf("%d\n",num);
            while(!que.empty())
            {
                int top=que.front();
                printf("%d %d\n",se[top].l,se[top].r);
                que.pop();
            }
        }
        else
            printf("No solution\n");
    //}
    return 0;
}