[已解决]如题

chenwhccc

n 个人去看电影，本来每人要买一张票，但电影院推出了一个活动：一个身高为 x 的人可以和身高至少为 2x 组合，两人一共只需买一张票。现在给出全体 n 个人的身高，请问总共至少要买多少电影票？

输入格式
第一行一个整数 n，代表总人数。

第二行 n 个整数，每个数 Ai
​
  代表每个人的身高。

输出格式
一个整数，表示最少需要购买的电影票数量。

数据范围
1<=n<=5*10的5次方
1<=Ai<=10的5次方

最佳答案

月排行榜 / 总排行榜

jhq999

2021-11-24 17:08:58

chenwhccc 发表于 2021-11-24 16:31
结果输出不了

别忘了先从小到大排序

int main()
{
        int n[]={1,2,3,4,5,8,10,14,15,17,20};
        int num=11,len=11;
        //scanf("%d",&n);
        while(1)
        {
                int i,j;
                for( i=0;i<len;i++)
                {
                        if(n[i]*2>n[len-1])
                                break;

                }
                int fj=i,flag=1;
                for(i=fj-1;i>=0;i--)
                {
                        for(j=fj;j<len;j++)//j++
                        {
                                if(n[j]>=2*n[i])
                                {
                                        flag=0;
                                        num--;
                                        n[i]=n[j]=0;
                                        break;
                                }
                        }
                }
                int tmp=len;
                j=0;
                while(n[j++]);
                j--;
                for(i=j;i<tmp;i++)
                {
                        if(n[i]==0)
                        {
                                len--;
                        }
                        else 
                        {
                                
                                
                                n[j++]=n[i];
                                n[i]=0;
                        }
                        
                }

                if(flag)  break;


        }
        printf("%d",num);
        return 0;
}

跳转到最佳答案楼层

jhq999

我说没这么简单吗！至少很缺德

数组[]先从小到大排序
num=len=数组大小//num代表正常买票的票数

while(1)
{

for(i=0;i<len：i++)if(数组[i]*2>数组[len-1])break;
fj=i;
flag=1；
for(i=fj-1;i>=0：i--)//例如：1,2，3,4，5，8，10，14，15，17，20。len=11,fj=8,i=10开始10和20，8和17，5和15，4和14 剩下1，2，3,num=len-4=7;
                             //1,2,3 len=3 fj=1,i=0,1和2 num-1=6;
{
   for(j=fj;j<len;j++)
   {
      if(数组[j]>=2*数组[i])
      {
         flag=0;
         num--;//2个人一张票，所以票数减一
         数组[i]=数组[j]=0;//已经配完对不再参与配对
         break;
       }
    
    }

}
for(i=0,j=0;i<len-1：i++)//结果数组=1，2，3，0，0，0……len=3//
{
  if(数组[i]==0)
   {
     len--;
   }
   else
       数组[j++]=数组[i]，数组[i]=0;
}

if(flag)break;
}
}
//num就是配对后的票数

chenwhccc

jhq999 发表于 2021-11-23 17:49
我说没这么简单吗！至少很缺德

感谢

chenwhccc

jhq999 发表于 2021-11-23 17:49
我说没这么简单吗！至少很缺德

是要定义两个数组吗？

chenwhccc

jhq999 发表于 2021-11-23 17:49
我说没这么简单吗！至少很缺德

#include <stdio.h>
int main()
{
        int n[5000000];
        int num=0,len;
        scanf("%d",&n);
        while(1)
        {
                int i,j;
                for( i=0;i<len;i++)
                {
                        if(n[i]*2>n[len-1])
                        break;
                        num=i+len-1;
                }
                int fj=i,flag=1;
                for(i=fj-1;i>=0;i--)
                {
                        for(j=fj;j<len-1;i++)
                        {
                                if(n[j]>=2*n[i])
                                {
                                        flag=0;
                                        num--;
                                        break;
                                }
                        }
                }
                for(int i=0,j=0;i<len-1;i++)
                {
                if(n[i]==0)
                {
                        len--;
                        
                }
                else
                n[j++]=n[i],n[i]=0;
                if(flag)  break;
                num=len+i-1;
        }
}
    print("%d",num);
        return 0;
}

chenwhccc

chenwhccc 发表于 2021-11-24 16:28

结果输出不了

jhq999

chenwhccc 发表于 2021-11-24 16:31
结果输出不了

别忘了先从小到大排序

int main()
{
        int n[]={1,2,3,4,5,8,10,14,15,17,20};
        int num=11,len=11;
        //scanf("%d",&n);
        while(1)
        {
                int i,j;
                for( i=0;i<len;i++)
                {
                        if(n[i]*2>n[len-1])
                                break;

                }
                int fj=i,flag=1;
                for(i=fj-1;i>=0;i--)
                {
                        for(j=fj;j<len;j++)//j++
                        {
                                if(n[j]>=2*n[i])
                                {
                                        flag=0;
                                        num--;
                                        n[i]=n[j]=0;
                                        break;
                                }
                        }
                }
                int tmp=len;
                j=0;
                while(n[j++]);
                j--;
                for(i=j;i<tmp;i++)
                {
                        if(n[i]==0)
                        {
                                len--;
                        }
                        else 
                        {
                                
                                
                                n[j++]=n[i];
                                n[i]=0;
                        }
                        
                }

                if(flag)  break;


        }
        printf("%d",num);
        return 0;
}

chenwhccc

jhq999 发表于 2021-11-24 17:08
别忘了先从小到大排序

老哥我感觉你好像审错题了

chenwhccc

chenwhccc 发表于 2021-11-24 23:29
老哥我感觉你好像审错题了

最后结果是输入两个量
一个是人数
一个是人数各自的身高
例如输入6
197355
输出4
因为1973买两张票55需要两张票

jhq999

chenwhccc 发表于 2021-11-24 23:31
最后结果是输入两个量
一个是人数
一个是人数各自的身高

输入和排序你自己不会写啊？而且自己要学会变通，身高我用整数单位是CM，你自己改成浮点也行,单位M

chenwhccc

jhq999 发表于 2021-11-25 06:05
输入和排序你自己不会写啊？而且自己要学会变通，身高我用整数单位是CM，你自己改成浮点也行,单位M

我用那个冒泡排序挺麻烦的

jhq999

chenwhccc 发表于 2021-11-25 15:58
我用那个冒泡排序挺麻烦的

//多写写代码你就会发现很简单，输入不用我写了吧
int i,j,tmp;//别忘了把这些变量在后面的声明去掉，初始化留下
for(i=0;i<len-1;i++)//选择法
for(j=i+1;j<len;j++)
{
  if(n[i]>n[j])
  {
     tmp=n[i];
    n[i]=n[j];
    n[j]=tmp;
   }
}

chenwhccc

能讲讲解题思路吗？我想优化一些算法，这个复杂度有点高。

tomok

看看算法

chenwhccc

tomok 发表于 2021-11-27 21:58
看看算法

属实看不懂了 救救我吧

chenwhccc

jhq999 发表于 2021-11-25 16:15

一直提示
printf was not declear in this scope

lightninng

chenwhccc 发表于 2021-11-27 19:12
能讲讲解题思路吗？我想优化一些算法，这个复杂度有点高。

说几句实话，如有冒犯，请包涵~~
冒泡排序你都觉得麻烦，就不要谈时间复杂度问题了~~~
另外说一句，冒泡算法的时间复杂度是哦o(n^2)，已经很高了，建议你先把几个常见的排序算法都自己手动实现一下，选择、插入、冒泡、快速、归并排序、堆排序等等~~

chenwhccc

jhq999 发表于 2021-11-23 17:49
我说没这么简单吗！至少很缺德

#include <stdio.h>
#include <stdlib.h>
int main()
{
        int n,i,j,num[500000],len=num[500000];
        scanf("%d",&n);
        scanf("%d",&num[500000]);
        {
                int tmp;
                tmp=num[i];
                num[i]=num[j];
                num[j]=tmp;
        }
     while(1)
        {
                for( i=0;i<len;i++)
                {
                        if(num[i]*2>num[len-1])
                                break;

                }
                int fj=i,flag=1;
                for(i=fj-1;i>=0;i--)
                {
                        for(j=fj;j<len;j++)
                        {
                                if(num[j]>=2*num[i])
                                {
                                        flag=0;
                                
                                        num[i]=num[j]=0;
                                        break;
                                }
                        }
                }
                int tmp=len;
                j=0;
                while(num[j++]);
                j--;
                for(i=j;i<tmp;i++)
                {
                        if(num[i]==0)
                        {
                                len--;
                        }
                        else 
                        {
                                
                                
                                num[j++]=num[i];
                                num[i]=0;
                        }
                        
                }

                if(flag)  break;
            }
        printf("%d",num);
        return 0;
}