URAL 1303 Minimal Coverage

URAL 1303

思路：

dp+贪心，然后记录路径

mx[i]表示从i开始最大可以到的位置

sufmx[i]表从1-i的某个位置开始最大可以到达的位置

比普通的贪心效率要高很多

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mp make_pair

#define pii pair<int,int>

#define mem(a,b) memset(a,b,sizeof(a))

const int N=1e5+;

int l[N],r[N];

int mx[N],sufmx[N];

int id[N],iid[N];

vector<int>ans;

int main(){

    ios::sync_with_stdio(false);

    cin.tie();

    int m,L,R;

    while(cin>>m){

        int c=;

        mem(mx,-);

        mem(id,-);

        mem(iid,-);

        ans.clear();

        while(cin>>L>>R){

            if(L==&&R==)break;

            c++;

            l[c]=L;

            r[c]=R;

            if(R>=){

                if(L<=)L=;

                if(R>mx[L])mx[L]=R,id[L]=c;

            }

        }

        sufmx[]=mx[];

        iid[]=id[];

        for(int i=;i<=5e4;i++)

        {

            if(mx[i]>sufmx[i-])sufmx[i]=mx[i],iid[i]=id[i];

            else sufmx[i]=sufmx[i-],iid[i]=iid[i-];

        }

        c=;

        bool f=false;

        while(true){

            if(sufmx[c]>=m){

                ans.pb(c);

                break;

            }

            if(sufmx[c]>c){

                ans.pb(c);

                c=sufmx[c];

            }

            else {

                f=true;

                break;

            }

        }

        if(f){

            cout<<"No solution"<<endl;

            continue;

        }

        cout<<ans.size()<<endl;

        for(int i=;i<ans.size();i++)cout<<l[iid[ans[i]]]<<' '<<r[iid[ans[i]]]<<endl;

    }

    return ;

}