Question

C语言高手 帮忙看一下 以前NOIP的一个题目

From leocy002
纪念品分组 全国青少年信息学奥林匹克分区联赛 (NOIp) 竞赛原题

描述 Description
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

【限制】

50%的数据满足: 1 <=n <= 15

100%的数据满足: 1 <= n <= 30000， 80 <= W <= 200

输入格式 Input Format
第1行包括一个整数w，为每组纪念品价格之和的上限= 第2行为一个整数n，表示购来的纪念品的总件数G

第3-n+2行每行包含一个正整数Pi (5 <= Pi <= w3)w表示所对应纪念品的价格。

输出格式 Output Format
仅1行，包含一个整数， ep最少的分组数目和

100
9
90
20
20
30
50
60
70
80
90

pur out:
6

#include <stdio.h>

int main()
{
int i,j,w,n, temp,number=0, a[500000];
scanf("%d", &w);
scanf("%d", &n);

for(i=1; i<=n; i++)
scanf("%d", &a[i]);

for(i=0;i<=n-1;i++)
for(j=1;j<n-i;j++)
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}

i=1,j=n;
while(i<=j)
{
if(i==j)
{ number++;
j--;}

else
if(a[i]+a[j]>w)
{
number++;
j--;
}

else if(a[i]+a[j]<=w)
{number++;
i++;
j--;
}

}

printf("%d",number);
return 0;

}

这是我的程序~!
这一题用贪心策略完全可以的.
先排序 然后两头放指针往中间移~!~!
可是为什么我 的方法在VIJOS上超时 谁帮我看一下
100分 只过了六个点 ??
别人怎么就可以过? 我哪里的效率出了问题 看一下 等

Answer 1

1、你用的排序是冒泡排序，是最慢的。最少也用个选择排序吧？！仔细查查各 种排序算法的效率。
2、把while(i<=j)改成i<j,把if(i==j）这语句单拿出来放到while后面（外面）去执行。可以节省判断次数。这条你仔细想想。
3、数组a太大了，30001就够了吧？节约分配管理内存的时间。(想再快，把int a[]变成unsigned char a[])

最后，程序是对的，就是不精益求精。

ps:分数为O，太小气了吧？！