10148 - Advertisement-----贪心，区间选点问题------水题
#include<cstdlib>#include<iostream>#include<cstdio>#include<cmath>#include<set>#include<cstring>#include <algorithm>#define inf 0x7fffffff#define N 1000#define MIN 1e-11#define M 10001#define MM 20020#define LL long longusing namespace std;int n,t,k;struct S{ int a,b;};int v[MM];S s[N];int cmp(S s1,S s2){ return s1.b<s2.b;}int main(){#ifndef ONLINE_JUDGE freopen("ex.in","r",stdin);#endif scanf("%d",&t); while(t--) { memset(v,0,sizeof(v)); scanf("%d%d",&k,&n); int minv=inf,maxv=-inf; for(int i=0; i<n; ++i) { scanf("%d%d",&s[i].a,&s[i].b); if(s[i].a>s[i].b) swap(s[i].a,s[i].b); if(minv>s[i].a) minv=s[i].a; if(minv>s[i].b) minv=s[i].b; if(maxv<s[i].b) maxv=s[i].b; if(maxv<s[i].a) maxv=s[i].a; } sort(s,s+n,cmp);// for(int i=0;i<n;i++)// cout<<"i="<<i<<" "<<s[i].a<<" "<<s[i].b<<endl; int num,cnt,count=0; for(int i=0; i<n; ++i) { if(s[i].b-s[i].a+1<=k) { for(int j=s[i].a; j<=s[i].b; j++) if(!v[j+M]) { count++; v[j+M]=1; } } else { cnt=0; for(int j=s[i].a; j<=s[i].b; j++) { if(v[j+M]) cnt++; if(cnt>=k) break; } num=0; cnt=k-cnt; for(int j=s[i].b; j>=s[i].a; j--) { if(num==cnt) break; if(!v[j+M]) { count++; num++; v[j+M]=1; } } } } printf("%d\n",count); for(int i=minv;i<=maxv;i++) if(v[i+M]) printf("%d\n",i); if(t) { printf("\n"); } } return 0;}