Is Bigger Smarter?

Is Bigger Smarter?

时间: 1ms        内存:64M

描述:

Some people think that the bigger an elephant is, the smarter it is. To disprove this, you want to analyze a collection of elephants and place as large a subset of elephants as possible into a sequence whose weights are increasing but IQ's are decreasing.

输入:

The input will consist of data for a bunch of elephants, at one elephant per line terminated by the end-of-file. The data for each particular elephant will consist of a pair of integers: the first representing its size in kilograms and the second representing its IQ in hundredths of IQ points. Both integers are between 1 and 10,000. The data contains information on at most 1,000 elephants. Two elephants may have the same weight, the same IQ, or even the same weight and IQ.

输出:

The first output line should contain an integer n, the length of elephant sequence found. The remaining n lines should each contain a single positive integer representing an elephant. Denote the numbers on the ith data line as W[i] and S[i]. If these sequence of n elephants are a[1], a[2],..., a[n] then it must be the case that W[a[1]] < W[a[2]] < ... < W[a[n]] and S[a[1]] > S[a[2]] > ... > S[a[n]] In order for the answer to be correct, n must be as large as possible. All inequalities are strict: weights must be strictly increasing, and IQs must be strictly decreasing. Your program can report any correct answer for a given input.

示例输入:

6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900

示例输出:

4
4
5
9
7

提示:

参考答案(内存最优[776]):

#include<stdio.h>
#define N 1005
FILE *f1,*f2;
typedef struct node
{
        long w,s,num;
}node;
node a[N];
long f[N],b[N],q[N],n;

int bigger(node x,node y)
{
     if (x.w!=y.w) return (x.w>y.w);
     else return (x.s<y.s);
}

void sort(long left,long right)
{
     long i,j;
     node x,t;
     i=left;j=right;
     x=a[(i+j)/2];
     while (i<=j)
     {
           while (bigger(x,a[i])) i++;
           while (bigger(a[j],x)) j--;
           if (i<=j)
           {     t=a[i];a[i]=a[j];a[j]=t;
                 i++;j--;
           }
     }
     if (left<j) sort(left,j);
     if (i<right) sort(i,right);
}
int main()
{
    long i,j,k,max;
    i=1;
    while (scanf("%ld%ld",&a[i].w,&a[i].s)==2)  a[i].num=i++;  
    n=i-1;
    sort(1,n);
    for (i=1;i<=n;i++) {f[i]=1;b[i]=i;}
    for (i=1;i<=n;i++)
        for (j=1;j<i;j++)
            if (a[j].w<a[i].w&&a[j].s>a[i].s&&f[j]+1>f[i])
            {  f[i]=f[j]+1; b[i]=j; }
    max=0;
    for (i=1;i<=n;i++)
        if (f[i]>max) {max=f[i];k=i;}
    printf("%ld\n",max);
    q[1]=a[k].num; i=1;
    while (b[k]!=k) {q[++i]=a[b[k]].num; k=b[k];}
    for (i=max;i>=1;i--)
        printf("%ld\n",q[i]);
    return 0;
}

参考答案(时间最优[0]):

#include<stdio.h> 
#define N 1005 
FILE *f1,*f2; 
typedef struct node 
{ 
        long w,s,num; 
}node; 
node a[N]; 
long f[N],b[N],q[N],n; 
  
int bigger(node x,node y) 
{ 
     if (x.w!=y.w) return (x.w>y.w); 
     else return (x.s<y.s); 
} 
  
void sort(long left,long right) 
{ 
     long i,j; 
     node x,t; 
     i=left;j=right; 
     x=a[(i+j)/2]; 
     while (i<=j) 
     { 
           while (bigger(x,a[i])) i++; 
           while (bigger(a[j],x)) j--; 
           if (i<=j) 
           {     t=a[i];a[i]=a[j];a[j]=t; 
                 i++;j--; 
           } 
     } 
     if (left<j) sort(left,j); 
     if (i<right) sort(i,right); 
} 
int main() 
{ 
    long i,j,k,max; 
    i=1; 
    while (scanf("%ld%ld",&a[i].w,&a[i].s)==2)  a[i].num=i++;   
    n=i-1; 
    sort(1,n); 
    for (i=1;i<=n;i++) {f[i]=1;b[i]=i;} 
    for (i=1;i<=n;i++) 
        for (j=1;j<i;j++) 
            if (a[j].w<a[i].w&&a[j].s>a[i].s&&f[j]+1>f[i]) 
            {  f[i]=f[j]+1; b[i]=j; } 
    max=0; 
    for (i=1;i<=n;i++) 
        if (f[i]>max) {max=f[i];k=i;} 
    printf("%ld\n",max); 
    q[1]=a[k].num; i=1; 
    while (b[k]!=k) {q[++i]=a[b[k]].num; k=b[k];} 
    for (i=max;i>=1;i--) 
        printf("%ld\n",q[i]); 
    return 0; 
} 

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注