[已解决]如题

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
结果输出不了

别忘了先从小到大排序

1. int main()
   
2. {
   
3.         int n[]={1,2,3,4,5,8,10,14,15,17,20};
   
4.         int num=11,len=11;
   
5.         //scanf("%d",&n);
   
6.         while(1)
   
7.         {
   
8.                 int i,j;
   
9.                 for( i=0;i<len;i++)
   
10.                 {
    
11.                         if(n[i]*2>n[len-1])
    
12.                                 break;
    
13. 
    
14.                 }
    
15.                 int fj=i,flag=1;
    
16.                 for(i=fj-1;i>=0;i--)
    
17.                 {
    
18.                         for(j=fj;j<len;j++)//j++
    
19.                         {
    
20.                                 if(n[j]>=2*n[i])
    
21.                                 {
    
22.                                         flag=0;
    
23.                                         num--;
    
24.                                         n[i]=n[j]=0;
    
25.                                         break;
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.                 int tmp=len;
    
30.                 j=0;
    
31.                 while(n[j++]);
    
32.                 j--;
    
33.                 for(i=j;i<tmp;i++)
    
34.                 {
    
35.                         if(n[i]==0)
    
36.                         {
    
37.                                 len--;
    
38.                         }
    
39.                         else
    
40.                         {
    
41.                                
    
42.                                
    
43.                                 n[j++]=n[i];
    
44.                                 n[i]=0;
    
45.                         }
    
46.                        
    
47.                 }
    
48. 
    
49.                 if(flag)  break;
    
50. 
    
51. 
    
52.         }
    
53.         printf("%d",num);
    
54.         return 0;
    
55. }

复制代码

跳转到最佳答案楼层

jhq999

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

1. 数组[]先从小到大排序
   
2. num=len=数组大小//num代表正常买票的票数
   
3. 
   
4. while(1)
   
5. {
   
6. 
   
7. for(i=0;i<len：i++)if(数组[i]*2>数组[len-1])break;
   
8. fj=i;
   
9. flag=1；
   
10. 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;
    
11.                              //1,2,3 len=3 fj=1,i=0,1和2 num-1=6;
    
12. {
    
13.    for(j=fj;j<len;j++)
    
14.    {
    
15.       if(数组[j]>=2*数组[i])
    
16.       {
    
17.          flag=0;
    
18.          num--;//2个人一张票，所以票数减一
    
19.          数组[i]=数组[j]=0;//已经配完对不再参与配对
    
20.          break;
    
21.        }
    
22.    
    
23.     }
    
24. 
    
25. }
    
26. for(i=0,j=0;i<len-1：i++)//结果数组=1，2，3，0，0，0……len=3//
    
27. {
    
28.   if(数组[i]==0)
    
29.    {
    
30.      len--;
    
31.    }
    
32.    else
    
33.        数组[j++]=数组[i]，数组[i]=0;
    
34. }
    
35. 
    
36. if(flag)break;
    
37. }
    
38. }
    
39. //num就是配对后的票数

复制代码

chenwhccc

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

感谢

chenwhccc

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

是要定义两个数组吗？

chenwhccc

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

1. #include <stdio.h>
   
2. int main()
   
3. {
   
4.         int n[5000000];
   
5.         int num=0,len;
   
6.         scanf("%d",&n);
   
7.         while(1)
   
8.         {
   
9.                 int i,j;
   
10.                 for( i=0;i<len;i++)
    
11.                 {
    
12.                         if(n[i]*2>n[len-1])
    
13.                         break;
    
14.                         num=i+len-1;
    
15.                 }
    
16.                 int fj=i,flag=1;
    
17.                 for(i=fj-1;i>=0;i--)
    
18.                 {
    
19.                         for(j=fj;j<len-1;i++)
    
20.                         {
    
21.                                 if(n[j]>=2*n[i])
    
22.                                 {
    
23.                                         flag=0;
    
24.                                         num--;
    
25.                                         break;
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.                 for(int i=0,j=0;i<len-1;i++)
    
30.                 {
    
31.                 if(n[i]==0)
    
32.                 {
    
33.                         len--;
    
34.                        
    
35.                 }
    
36.                 else
    
37.                 n[j++]=n[i],n[i]=0;
    
38.                 if(flag)  break;
    
39.                 num=len+i-1;
    
40.         }
    
41. }
    
42.     print("%d",num);
    
43.         return 0;
    
44. }

复制代码

chenwhccc

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

结果输出不了

jhq999

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

别忘了先从小到大排序

1. int main()
   
2. {
   
3.         int n[]={1,2,3,4,5,8,10,14,15,17,20};
   
4.         int num=11,len=11;
   
5.         //scanf("%d",&n);
   
6.         while(1)
   
7.         {
   
8.                 int i,j;
   
9.                 for( i=0;i<len;i++)
   
10.                 {
    
11.                         if(n[i]*2>n[len-1])
    
12.                                 break;
    
13. 
    
14.                 }
    
15.                 int fj=i,flag=1;
    
16.                 for(i=fj-1;i>=0;i--)
    
17.                 {
    
18.                         for(j=fj;j<len;j++)//j++
    
19.                         {
    
20.                                 if(n[j]>=2*n[i])
    
21.                                 {
    
22.                                         flag=0;
    
23.                                         num--;
    
24.                                         n[i]=n[j]=0;
    
25.                                         break;
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.                 int tmp=len;
    
30.                 j=0;
    
31.                 while(n[j++]);
    
32.                 j--;
    
33.                 for(i=j;i<tmp;i++)
    
34.                 {
    
35.                         if(n[i]==0)
    
36.                         {
    
37.                                 len--;
    
38.                         }
    
39.                         else
    
40.                         {
    
41.                                
    
42.                                
    
43.                                 n[j++]=n[i];
    
44.                                 n[i]=0;
    
45.                         }
    
46.                        
    
47.                 }
    
48. 
    
49.                 if(flag)  break;
    
50. 
    
51. 
    
52.         }
    
53.         printf("%d",num);
    
54.         return 0;
    
55. }

复制代码

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
我用那个冒泡排序挺麻烦的

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

复制代码

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
我说没这么简单吗！至少很缺德

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. int main()
   
4. {
   
5.         int n,i,j,num[500000],len=num[500000];
   
6.         scanf("%d",&n);
   
7.         scanf("%d",&num[500000]);
   
8.         {
   
9.                 int tmp;
   
10.                 tmp=num[i];
    
11.                 num[i]=num[j];
    
12.                 num[j]=tmp;
    
13.         }
    
14.      while(1)
    
15.         {
    
16.                 for( i=0;i<len;i++)
    
17.                 {
    
18.                         if(num[i]*2>num[len-1])
    
19.                                 break;
    
20. 
    
21.                 }
    
22.                 int fj=i,flag=1;
    
23.                 for(i=fj-1;i>=0;i--)
    
24.                 {
    
25.                         for(j=fj;j<len;j++)
    
26.                         {
    
27.                                 if(num[j]>=2*num[i])
    
28.                                 {
    
29.                                         flag=0;
    
30.                                 
    
31.                                         num[i]=num[j]=0;
    
32.                                         break;
    
33.                                 }
    
34.                         }
    
35.                 }
    
36.                 int tmp=len;
    
37.                 j=0;
    
38.                 while(num[j++]);
    
39.                 j--;
    
40.                 for(i=j;i<tmp;i++)
    
41.                 {
    
42.                         if(num[i]==0)
    
43.                         {
    
44.                                 len--;
    
45.                         }
    
46.                         else
    
47.                         {
    
48.                                 
    
49.                                 
    
50.                                 num[j++]=num[i];
    
51.                                 num[i]=0;
    
52.                         }
    
53.                         
    
54.                 }
    
55. 
    
56.                 if(flag)  break;
    
57.             }
    
58.         printf("%d",num);
    
59.         return 0;
    
60. }

复制代码