合并果子

他的意思是说， 只能过第一组和第十组数据

合并果子， 以前的省赛题

算法就是贪心，

每次取数据中最小的两个，合并后再插入

因为每次合并都有插入操作，所以插入排序是不够好的

这样的效率是 O(n^2)

普遍做法是使用 堆结构 来维护这组数据

堆是一种比较简单的数据结构

可以尝试实现

再不然，你可以用stl中的 priority_queue
#include 就可以了

它就是堆结构的一个实现

我大概看了你的程序，没有发现什么问题

不甘心， 我自己试了一下
确实只能过两个数据

我又稍微修改了一些，

编译通过...
├ 测试数据 01：答案正确... 212ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 119ms
├ 测试数据 08：答案正确... 228ms
├ 测试数据 09：答案正确... 134ms
├ 测试数据 10：答案正确... 228ms

#include
#include
int a[10005];

int cmp(const void* a,const void* b){
return *(int*)a-*(int*)b;
}

int main() {
int n, i, j;
int t = 0, x;
scanf("%d", &n);
for (i = 0; i < n; i++) scanf("%d", &a[i]);
qsort(a,n,sizeof(a[0]),cmp);
for (i = 1; i < n; i++) {
a[i] += a[i - 1];
t += a[i];
for (j = i; j < n-1 && a[j] > a[j + 1]; j++) {
x = a[j];
a[j] = a[j + 1];
a[j + 1] = x;
}
}
printf("%d", t);

return 0;
}

上面是原程序，只是更改了快排

看来是你快排有问题

你那快排确实不大优美， 也许有些小毛病

void qs(int *s,int l,int r){
if(r<=l)return;
int i=l,j=r,t=s[i];
while(i while(i while(i }
s[i]=t;
qs(s,l,i-1);
qs(s,i+1,r);
}
这个是我以前写的，测试了一下
├ 测试数据 01：答案正确... 494ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 56ms
├ 测试数据 07：答案正确... 291ms
├ 测试数据 08：答案正确... 494ms
├ 测试数据 09：答案正确... 291ms
├ 测试数据 10：答案正确... 478ms

效率果然没有标准的qsort高，估计有优化

你对比一下快排，再改改看

下面是堆结构的成绩及代码

编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms

#include
#include
using namespace std;
priority_queue,greater > q;

int main(){
int n,x;
scanf("%d",&n);
for (;n--;q.push(x))
scanf("%d",&x);

for(x=0;!q.empty();q.push(n)){
n=q.top(); q.pop();
if(q.empty())break;
n+=q.top(); q.pop();
x+=n;
}
printf("%d",x);
return 0;
}

我以前参加过noip， 所以有兴趣

tazerkinq@163.com

他的意思是说，
只能过第一组和第十组数据
合并果子，
以前的省赛题
算法就是贪心，
每次取数据中最小的两个，合并后再插入
因为每次合并都有插入操作，所以插入排序是不够好的
这样的效率是
O(n^2)
普遍做法是使用
堆结构
来维护这组数据
堆是一种比较简单的数据结构
可以尝试实现
再不然，你可以用stl中的
priority_queue
#include

就可以了
它就是堆结构的一个实现
我大概看了你的程序，没有发现什么问题
不甘心，
我自己试了一下
确实只能过两个数据
我又稍微修改了一些，
编译通过...
├
测试数据
01：答案正确...
212ms
├
测试数据
02：答案正确...
0ms
├
测试数据
03：答案正确...
0ms
├
测试数据
04：答案正确...
0ms
├
测试数据
05：答案正确...
0ms
├
测试数据
06：答案正确...
0ms
├
测试数据
07：答案正确...
119ms
├
测试数据
08：答案正确...
228ms
├
测试数据
09：答案正确...
134ms
├
测试数据
10：答案正确...
228ms
#include

#include

int
a[10005];
int
cmp(const
void*
a,const
void*
b){
return
*(int*)a-*(int*)b;
}
int
main()
{
int
n,
i,
j;
int
t
=
0,
x;
scanf("%d",
&n);
for
(i
=
0;
i
<
n;
i++)
scanf("%d",
&a[i]);
qsort(a,n,sizeof(a[0]),cmp);
for
(i
=
1;
i
<
n;
i++)
{
a[i]
+=
a[i
-
1];
t
+=
a[i];
for
(j
=
i;
j
<
n-1
&&
a[j]
>
a[j
+
1];
j++)
{
x
=
a[j];
a[j]
=
a[j
+
1];
a[j
+
1]
=
x;
}
}
printf("%d",
t);
return
0;
}
上面是原程序，只是更改了快排
看来是你快排有问题
你那快排确实不大优美，
也许有些小毛病
void
qs(int
*s,int
l,int
r){
if(r<=l)return;
int
i=l,j=r,t=s[i];
while(iwhile(iwhile(i}
s[i]=t;
qs(s,l,i-1);
qs(s,i+1,r);
}
这个是我以前写的，测试了一下
├
测试数据
01：答案正确...
494ms
├
测试数据
02：答案正确...
0ms
├
测试数据
03：答案正确...
0ms
├
测试数据
04：答案正确...
0ms
├
测试数据
05：答案正确...
0ms
├
测试数据
06：答案正确...
56ms
├
测试数据
07：答案正确...
291ms
├
测试数据
08：答案正确...
494ms
├
测试数据
09：答案正确...
291ms
├
测试数据
10：答案正确...
478ms
效率果然没有标准的qsort高，估计有优化
你对比一下快排，再改改看
下面是堆结构的成绩及代码
编译通过...
├
测试数据
01：答案正确...
0ms
├
测试数据
02：答案正确...
0ms
├
测试数据
03：答案正确...
0ms
├
测试数据
04：答案正确...
0ms
├
测试数据
05：答案正确...
0ms
├
测试数据
06：答案正确...
0ms
├
测试数据
07：答案正确...
0ms
├
测试数据
08：答案正确...
0ms
├
测试数据
09：答案正确...
0ms
├
测试数据
10：答案正确...
0ms
#include
#include
using
namespace
std;
priority_queue,greater
>
q;
int
main(){
int
n,x;
scanf("%d",&n);
for
(;n--;q.push(x))
scanf("%d",&x);
for(x=0;!q.empty();q.push(n)){
n=q.top();
q.pop();
if(q.empty())break;
n+=q.top();
q.pop();
x+=n;
}
printf("%d",x);
return
0;
}
我以前参加过noip，
所以有兴趣
tazerkinq@163.com

为什么只能过2个点（1点和10点）
什么意思？说明下！