题目描述
农夫约翰想给他的N (2 <= N <= 1,000,000,000) 头牛照相,这些牛站成一排分别编号为1..N。每张照片可以拍摄连续的一些牛,并且约翰想让每头牛至少出现在一张照片上。
不幸的是有一些牛脾气不合,不想出现在同一张照片上,不合的牛有K(1 <= K <= 1000)对。给出这K对不合关系,算一下约翰最少需要拍多少张照片。
输入
第1行,两个整数N和K
第2到K+1行,每行两个数A和B,表示位置在A和B的两头牛不合,因此不能在同一张照片中。
输出
一个整数,表示约翰最少需要拍多少张照片数。
样例输入
7 3
1 3
2 4
5 6
样例输出
3
参考代码
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int a;
int b;
}
n;
n cow[1005];
n zz;
int main()
{
int n,k;
int x,y;
scanf("%d%d",&n,&k);
int j,i;
for (i=0;i<k;i++)
{
scanf("%d%d",&x,&y);
cow[i].a=x>y?y:x;
cow[i].b=x>y?x:y;
}
for (i=0;i<k;i++)
for (j=i+1;j<k;j++)
{
if(cow[i].a>cow[j].a)
{
zz=cow[i];
cow[i]=cow[j];
cow[j]=zz;
}
}
int sum=1;
int t=0;
int flag1,flag2;
for (i=t;i<k;i=t)
{
flag1=cow[i].a;
flag2=cow[i].b;
for (j=i+1;j<k;j++)
{
if(cow[j].a>=flag1&&cow[j].a<=flag2)
{
flag2=flag2>cow[j].b?cow[j].b:flag2;
t=j;
}
}
t=t+1;
sum++;
}
printf("%d",sum);
return 0;
}
解析
暂无