3222421_ac_204ms_1088k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

struct node
{
	int l, r;
	bool operator < (const node &x) const
	{
		if(l==x.l)
			return r < x.r;
		else
			return l < x.l;
	}
}itv[100001];

int main()
{
	int i, j, k, M;
	int l, r, t;
	int cnt, max, tmp;
	vector <node> ans;

	scanf("%d",&M);
	i = 0;
	ans.clear();
	while(scanf("%d%d",&l,&r)==2)
	{
		if(l==0&&r==0)
			break;
		itv[i].l = l;
		itv[i].r = r;
		i++;
	}
	sort(itv,itv+i);
	cnt = 0;
	max = 0;
	for(j = 0; j < i; j++)
	{
		if(max >= M)
			break;
		k = j;
		tmp = -10000000;
		while(k < i&&itv[k].l <= max)
		{
			if(itv[k].r > tmp)
			{
				tmp = itv[k].r;
				t = k;
			}
			k++;
		}
		if(tmp <= max)
		{
			cnt = 0;
			break;
		}
		max = tmp;
		cnt++;
		ans.push_back(itv[t]);
		j = k-1;
	}
	if(cnt==0)
	{
		puts("No solution");
	}
	else
	{
		printf("%d\n",cnt);
		for(i = 0; i < ans.size(); i++)
		{
			printf("%d %d\n",ans[i].l,ans[i].r);
		}
	}
	return 0;
}