如题
n 个人去看电影，本来每人要买一张票，但电影院推出了一个活动：一个身高为 x 的人可以和身高至少为 2x 组合，两人一共只需买一张票。现在给出全体 n 个人的身高，请问总共至少要买多少电影票？输入格式
第一行一个整数 n，代表总人数。
第二行 n 个整数，每个数 Ai
代表每个人的身高。
输出格式
一个整数，表示最少需要购买的电影票数量。
数据范围
1<=n<=5*10的5次方
1<=Ai<=10的5次方
本帖最后由 jhq999 于 2021-11-23 19:20 编辑
我说没这么简单吗！至少很缺德
数组[]先从小到大排序
num=len=数组大小//num代表正常买票的票数
while(1)
{
for(i=0;i<len：i++)if(数组*2>数组)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(数组>=2*数组)
{
flag=0;
num--;//2个人一张票，所以票数减一
数组=数组=0;//已经配完对不再参与配对
break;
}
}
}
for(i=0,j=0;i<len-1：i++)//结果数组=1，2，3，0，0，0……len=3//
{
if(数组==0)
{
len--;
}
else
数组=数组，数组=0;
}
if(flag)break;
}
}
//num就是配对后的票数 jhq999 发表于 2021-11-23 17:49
我说没这么简单吗！至少很缺德
感谢 jhq999 发表于 2021-11-23 17:49
我说没这么简单吗！至少很缺德
是要定义两个数组吗？ jhq999 发表于 2021-11-23 17:49
我说没这么简单吗！至少很缺德
#include <stdio.h>
int main()
{
int n;
int num=0,len;
scanf("%d",&n);
while(1)
{
int i,j;
for( i=0;i<len;i++)
{
if(n*2>n)
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>=2*n)
{
flag=0;
num--;
break;
}
}
}
for(int i=0,j=0;i<len-1;i++)
{
if(n==0)
{
len--;
}
else
n=n,n=0;
if(flag)break;
num=len+i-1;
}
}
print("%d",num);
return 0;
} chenwhccc 发表于 2021-11-24 16:28
结果输出不了 本帖最后由 jhq999 于 2021-11-24 17:19 编辑
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*2>n)
break;
}
int fj=i,flag=1;
for(i=fj-1;i>=0;i--)
{
for(j=fj;j<len;j++)//j++
{
if(n>=2*n)
{
flag=0;
num--;
n=n=0;
break;
}
}
}
int tmp=len;
j=0;
while(n);
j--;
for(i=j;i<tmp;i++)
{
if(n==0)
{
len--;
}
else
{
n=n;
n=0;
}
}
if(flag)break;
}
printf("%d",num);
return 0;
} jhq999 发表于 2021-11-24 17:08
别忘了先从小到大排序
老哥我感觉你好像审错题了 chenwhccc 发表于 2021-11-24 23:29
老哥我感觉你好像审错题了
最后结果是输入两个量
一个是人数
一个是人数各自的身高
例如输入6
197355
输出4
因为1973买两张票55需要两张票 本帖最后由 jhq999 于 2021-11-25 06:09 编辑
chenwhccc 发表于 2021-11-24 23:31
最后结果是输入两个量
一个是人数
一个是人数各自的身高
输入和排序你自己不会写啊？而且自己要学会变通，身高我用整数单位是CM，你自己改成浮点也行,单位M jhq999 发表于 2021-11-25 06:05
输入和排序你自己不会写啊？而且自己要学会变通，身高我用整数单位是CM，你自己改成浮点也行,单位M
我用那个冒泡排序挺麻烦的 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>n)
{
tmp=n;
n=n;
n=tmp;
}
}
能讲讲解题思路吗？我想优化一些算法，这个复杂度有点高。 看看算法
tomok 发表于 2021-11-27 21:58
看看算法
属实看不懂了 救救我吧 jhq999 发表于 2021-11-25 16:15
一直提示
printf was not declear in this scope{:5_104:} chenwhccc 发表于 2021-11-27 19:12
能讲讲解题思路吗？我想优化一些算法，这个复杂度有点高。
说几句实话，如有冒犯，请包涵~~
冒泡排序你都觉得麻烦，就不要谈时间复杂度问题了~~~
另外说一句，冒泡算法的时间复杂度是哦o(n^2)，已经很高了，建议你先把几个常见的排序算法都自己手动实现一下，选择、插入、冒泡、快速、归并排序、堆排序等等~~ jhq999 发表于 2021-11-23 17:49
我说没这么简单吗！至少很缺德
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,i,j,num,len=num;
scanf("%d",&n);
scanf("%d",&num);
{
int tmp;
tmp=num;
num=num;
num=tmp;
}
while(1)
{
for( i=0;i<len;i++)
{
if(num*2>num)
break;
}
int fj=i,flag=1;
for(i=fj-1;i>=0;i--)
{
for(j=fj;j<len;j++)
{
if(num>=2*num)
{
flag=0;
num=num=0;
break;
}
}
}
int tmp=len;
j=0;
while(num);
j--;
for(i=j;i<tmp;i++)
{
if(num==0)
{
len--;
}
else
{
num=num;
num=0;
}
}
if(flag)break;
}
printf("%d",num);
return 0;
}
页:
[1]