Đề bài: $\href{https://acm.timus.ru/problem.aspx?space=1&num=1303}{Đây}$
Tóm tắt: Cho một tập segment , và số M. Nhiệm vụ: In ra số tập tối thiểu cần dùng để phủ đoạn trên.
Source:
- #include<bits/stdc++.h>
- using namespace std;
- int m,p,a,b;
- struct xd{
- int s,e;
- bool operator < (const xd& a)const{
- return s<a.s;
- }
- }ss[100005];
- int vis[100005];
- int main(){
- p=0;
- memset(vis,0,sizeof vis);
- scanf("%d",&m);
- while(scanf("%d%d",&a,&b)){
- if(a==0&&b==0)break;
- if(b<=0||a>=m||a==b)continue;
- ss[p].s=a,ss[p].e=b;
- p++;
- }
- sort(ss,ss+p);
- int flag=1,ed=0,pos=0,tp=0;
- while(ed<m){
- int ned=0,ni=0;
- while(pos<p&&ss[pos].s<=ed){
- if(ss[pos].e>ned){
- ned=ss[pos].e;
- ni=pos;
- }
- pos++;
- }
- if(ned==0){flag=0;break;}
- ed=ned;
- vis[ni]=1;
- tp++;
- }
- if(p==0||flag==0){
- printf("No solution\n");
- }else{
- printf("%d\n",tp);
- for(int i=0;i<p;i++){
- if(vis[i])printf("%d %d\n",ss[i].s,ss[i].e);
- }
- }
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét