给牛照相

code

6 年前

给牛照相

时间： 1ms 内存：128M

描述：

农夫约翰想给他的N (2 <= N <= 1,000,000,000) 头牛照相，这些牛站成一排分别编号为1..N。每张照片可以拍摄连续的一些牛，并且约翰想让每头牛至少出现在一张照片上。

不幸的是有一些牛脾气不合，不想出现在同一张照片上，不合的牛有K(1 <= K <= 1000)对。给出这K对不合关系，算一下约翰最少需要拍多少张照片。

输入：

第1行，两个整数N和K

第2到K+1行，每行两个数A和B，表示位置在A和B的两头牛不合，因此不能在同一张照片中。

输出：

一个整数，表示约翰最少需要拍多少张照片数。

示例输入：

示例输出：

提示：

参考答案（内存最优[1128]）：

#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;
    }

参考答案（时间最优[3]）：

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstdio>
#include<cstdlib>
typedef struct node{
int a1;
int a2;
}node;
node a[1005];
bool cmp(node s,node k){
return s.a1 < k.a1;
}
int main(void){
    int n;//n头牛
    int k;//k对不和
    int x,y;
    scanf("%d%d",&n,&k);
    for(int i=0;i<k;i++){
        scanf("%d%d",&x,&y);
        a[i].a1=x>y?y:x;
        a[i].a2=x>y?x:y;
    }
    sort(a,a+k,cmp);
    int flag1,flag2;//左右边界
    int t=0;//下一次起始点
    int sum=1;//拍照数
    for(int u=t;u<k;u=t){
        flag1=a[u].a1;
        flag2=a[u].a2;
        for(int y=u+1;y<k;y++){
            if(a[y].a1>=flag1&&a[y].a1<=flag2){
                flag1=a[y].a1;
                flag2=a[y].a2>flag2?flag2:a[y].a2;
                t=y;
            }
        }
        t++;
        sum++;
    }
    printf("%d",sum);
return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。