合并果子c语言
① 合并果子 pascal
合并果子解题报告
1. 首先的思路是先排序，然后找到两个最小的，插入排序到原来的序列中，速度很慢
var a:array[0..10000] of longint;
n,total:longint;
i:integer;
procere swap(var a,b:longint);
var t:integer;
begin
t:=a; a:=b; b:=t
end;
procere quick_sort(m,n:integer);
var i,j,x:integer;
begin
i:=m; j:=n; x:=a[(i+j) div 2];
repeat
while a[i]>x do inc(i);
while x>a[j] do dec(j);
if i<=j then begin
swap(a[i],a[j]);
inc(i); dec(j)
end;
until i>j;
if m<j then quick_sort(m,j);
if i<n then quick_sort(i,n);
end;
procere insert_sort(n:integer);
var i,j:integer;
begin
i:=n-1; a[0]:=a[n];
while a[i]<a[0] do begin
a[i+1]:=a[i];
dec(i)
end;
a[i+1]:=a[0]
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
quick_sort(1,n);
for i:=1 to n-1 do begin
a[n-i]:=a[n-i]+a[n-i+1];
a[n-i+1]:=0;
inc(total,a[n-i]);
insert_sort(n-i)
end;
writeln(total);
end.
2. 我们可以通过堆排序找最小值
var a:array[0..20000] of longint;
i,j,n,ed,sum,t:longint;
procere heapdown(i,n:longint);
var j,t:longint;
begin
j:=i*2;
while j<=n do
begin
if (j<n) and (a[j+1]<a[j]) then inc(j);
if a[i]>a[j] then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
i:=j;
j:=i*2;
end
else j:=maxlongint;
end;
end;
begin
readln(n);
for i:=1 to n do
read(a[i]);
for i:=n div 2 downto 1 do
heapdown(i,n);
sum:=0;
while n<>1 do
begin
t:=a[n];a[n]:=a[1];a[1]:=t;
heapdown(1,n-1);
dec(n);
t:=a[n];a[n]:=a[1];a[1]:=t;
heapdown(1,n-1);
a[n]:=a[n]+a[n+1];
sum:=sum+a[n];
end;
writeln(sum);
end.
3. 我们可以通过维护两个单调队列来完成
var
tot:array[0..20000] of longint;
quea,queb:array[0..10000] of longint;
i,j,n,la,lb,ra,rb,x,max,k,a1,a2,b1,b2,sum:longint;
procere minx;
var i,j:longint;
begin
if (a1<b1) and (a2<b1) then
begin
inc(la,2);
inc(rb,1);
queb[rb]:=a1+a2;
dec(k);
sum:=sum+a1+a2;
exit;
end;
if (b1<a1) and (b2<a1) then
begin
inc(lb,2);
inc(rb,1);
queb[rb]:=b1+b2;
dec(k);
sum:=sum+b1+b2;
exit;
end;
inc(la,1);
inc(lb,1);
inc(rb,1);
queb[rb]:=a1+b1;
dec(k);
sum:=sum+a1+b1;
end;
begin
readln(n);
for i:=1 to n do
begin
read(x);
inc(tot[x]);
if x>max then max:=x;
end;
la:=1;lb:=1;ra:=0;rb:=0;
for i:=1 to max do
for j:=1 to tot[i] do
begin
inc(ra);
quea[ra]:=i;
end;
k:=n;
while k<>1 do
begin
a1:=0;a2:=0;b1:=0;b2:=0;
if la<=ra then a1:=quea[la] else a1:=maxlongint;
if la+1<=ra then a2:=quea[la+1] else a2:=maxlongint;
if lb<=rb then b1:=queb[lb] else b1:=maxlongint;
if lb+1<=rb then b2:=queb[lb+1] else b2:=maxlongint;
minx;
end;
writeln(sum);
end.
我的网站是www.tyvj.cn
欢迎交流
② C语言 合并果子问题
其他都写得不错但是算法出了点问题
正确的顺序应该是：排序－最小的两项相加－排序－最小的两项相加－排序－最小的两项相加－排序－最小的两项相加..........
而不是：排序－最小的两项相加－依次往后相加－........
给你一段我写的
#include<stdio.h>
#defineN100
intcount[N];
intmain()
{
intkind,i;
doublesum=0;
voidcompare(intm);
scanf("%d",&kind);
for(i=0;i<kind;i++)
scanf("%d",&count[i]);
for(i=0;i<kind-1;i++)
{
compare(kind);
sum+=count[0]+count[1];
count[0]=sum;
count[1]=count[kind-1]+1;
}
printf("%lf",sum);
return0;
}
voidcompare(intm)
{
inti,j;
for(i=0;i<m-1;i++)
for(j=i;j<m-i-1;j++)
if(count[j]>count[j+1])
{
count[j]=count[j]+count[j+1];
count[j+1]=count[j]-count[j+1];
count[j]=count[j]-count[j+1];
}
}
③ c++ 合并果子 求解哪错了
这位同学答得满好的
http://..com/link?url=-_icKCVe_RiaqhI_
你的程序是没问题
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
usingnamespacestd;
inta[10050]={0};
intsum[10050]={0};
intmain()
{
intn;
intsuma;
inti,j;
while(cin>>n){
suma=0;
for(i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1,greater<int>());
for(j=1;j<n;j++){
sum[j]=a[n-j+1]+a[n-j];
suma+=sum[j];
for(i=n-1-j;i>=1;i--){
if(sum[j]<a[i]){
for(intp=n-j-1;p>i;p--){
a[p+1]=a[p];
}
a[i+1]=sum[j];
break;
}
}
}
cout<<suma<<endl;
}
return0;
}
④ c++ 合并果子 边界处理问题
#include<iostream>
#include<algorithm>
usingnamespacestd;
#defineN10050
intmain()
{
unsignedlonga[N]={0};
unsignedlongsum[N]={0};
unsignedlongn;
unsignedlongsuma;
unsignedlongi,j;
unsignedlongp;
while(cin>>n){
for(i=0;i<N;i++)sum[i]=a[i]=0;
for(i=1;i<=n;i++)
cin>>a[i];
//边界检测
if(n==1){
cout<<a[1]<<endl;
continue;
}
sort(a+1,a+n+1,greater<unsignedlong>());
suma=0;
for(j=1;j<n;j++){//n-1次合并
sum[j]=a[n-j]+a[n-j+1];
suma=suma+sum[j];
for(i=n-j-1;i>=1;i--){
if(a[i]>=sum[j]){//找到一个比sum[j]大的
for(p=n-j-1;p>i;p--){//后移
a[p+1]=a[p];
}
a[i+1]=sum[j];//
a[n-j+1]=0;
break;
}
}
if(i==0){//sum[j]最大
for(p=n-j-1;p>=1;p--){
a[p+1]=a[p];
}
a[1]=sum[j];
}
}
cout<<suma<<endl;
}
return0;
}
⑤ pascal问题-合并果子
其实这道题用堆排做最快，首先应用大根堆将数据从小到大排一次，然后取第一个数，接着将最后一个数替换第一个数，用小根堆从第一个数调堆~~然后再取第一个数，和刚才取的数合并计算分，然后将合并以后的数放在第一个，然后用小根堆从第一个数调堆，一直重复这个动作~知道堆中只剩一个数。
下面是程序：
program ss1156;
type
ty=array[1..100000] of longint;
var
a:ty;
n:longint;
min:int64;
procere init;
var i:longint;
begin
readln(n);
for i:=1 to n do
read(a[i]);
end;
procere sift(i,n:longint);
var j,x:longint;finished:boolean;
begin
a[0]:=a[i]; j:=2*i; x:=a[i]; finished:=false;
while (j<=n) and (not finished) do
begin
if (j<n) and (a[j]<a[j+1]) then j:=j+1;
if x>=a[j] then finished:=true
else
begin
a[i]:=a[j]; i:=j; j:=i*2;
end;
end;
a[i]:=a[0];
end;
procere sift1(i,n:longint);
var j,x:longint;finished:boolean;
begin
a[0]:=a[i]; j:=2*i; x:=a[i]; finished:=false;
while (j<=n) and (not finished) do
begin
if (j<n) and (a[j]>a[j+1]) then j:=j+1;
if x<=a[j] then finished:=true
else
begin
a[i]:=a[j]; i:=j; j:=i*2;
end;
end;
a[i]:=a[0];
end;
procere main;
var i,j,v1,v2:longint;
begin
min:=0;
for i:=n div 2 downto 1 do sift(i,n);
for i:=n downto 2 do
begin
j:=a[1];
a[1]:=a[i];
a[i]:=j;
sift(1,i-1);
end;
for i:=1 to n-1 do
begin
v1:=a[1];
a[1]:=a[n-i+1];
sift1(1,n-i);
v2:=a[1];
a[1]:=a[1]+v1;
sift1(1,n-i);
min:=min+v1+v2;
end;
writeln(min);
end;
begin
init;
main;
end.
⑥ C语言 合并果子（类哈夫曼树）问题
这段代码恐怕达不到目的。有如下问题，看注释：
for(j=num;j>=0;j--){ //要改成j>0，因为j从num开始，到1就够数儿了
bubble_sort(a,n);
b[j-1]=a[j-1]+=a[j];//要改成b[j-1]=a[j-2]+=a[j-1]，因为j=num开始
n=n-1;
}
for(j=num;j>=0;j--){//改成j=num-1;j>0;j--。num就越界了，而b[0]还没有赋值，是随机的
total+=b[j];
}
//final=total-temp; 这句没有必要了
printf("%d",final);//改成printf("%d",total);
}
另：函数bubble_sort改成void型吧，无需返回值，实现中也没有……
以上意见仅供参考……
⑦ 初中C语言经典例题
1、求1+2+3+4+5+......+n
2、求1*2*3*4*5*......*n
3、求菲波拉契数列第n项（菲波拉契数列满足：A1 = 1；A2 = 1；An = An-1 + An-2（n>=3);
4、判断一个数能否分成两个合数的积
5、求两个数的最大公约数；
6、这是高中信息学奥林匹克竞赛2004年的复赛第一题，不过蛮简单的，推介做一下：
津津的储蓄计划
(save.c)
【问题描述】
津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。
为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上20%还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于100元或恰好100元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。
例如11月初津津手中还有83元，妈妈给了津津300元。津津预计11月的花销是180元，那么她就会在妈妈那里存200元，自己留下183元。到了11月月末，津津手中会剩下3元钱。
津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。
现在请你根据2004年1月到12月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到2004年年末，妈妈将津津平常存的钱加上20%还给津津之后，津津手中会有多少钱。
【输入文件】
输入文件save.in包括12行数据，每行包含一个小于350的非负整数，分别表示1月到12月津津的预算。
【输出文件】
输出文件save.out包括一行，这一行只包含一个整数。如果储蓄计划实施过程中出现某个月钱不够用的情况，输出-X，X表示出现这种情况的第一个月；否则输出到2004年年末津津手中会有多少钱。
【样例输入1】
290
230
280
200
300
170
340
50
90
80
200
60
【样例输出1】
-7
【样例输入2】
290
230
280
200
300
170
330
50
90
80
200
60
【样例输出2】
1580
数列基本：
1、找最大数：
找一组数中的最大数；
2、排序：
将N个数从小到大排列；
3、搜索：
在一个数列中找到一个数，并将其删除。
字符串处理相关：
1、解一元一次方程（该方程被直接作为字符串读入）：
-x+3x-18-9x+37-9x-1=2x+3-x
综合：
这里也同样给出一道题，尽可能优化程序效率：
合并果子
(fruit.c)
【问题描述】
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。
例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
【输入文件】
输入文件fruit.in包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=20000)是第i种果子的数目。
【输出文件】
输出文件fruit.out包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。
【样例输入】
3
1 2 9
【样例输出】
15
【数据规模】
对于30％的数据，保证有n<=1000：
对于50％的数据，保证有n<=5000；
对于全部的数据，保证有n<=10000。
⑧ C语言合并果子问题
#include<stdio.h>
int a[10001],b[10001],h1=1,h2=1,t1=1,t2=0,ans=0,num=0;
void qs(int left,int right)
{
if(left>=right) return;
int i=left,j=right;
a[0]=a[left];
while(i<j)
{
while(a[right]>=a[0]&&i<j) j--;
if(i<j)a[i]=a[j];
while(a[left]<=a[0]&&i<j) i++;
if(i<j) a[j]=a[i];
}
a[i]=a[0];
qs(left,i-1);
qs(i+1,right);
}
int main()
{
int n;
FILE *fp;
memset(a,5,sizeof(a));
fp=fopen("fruit.in","r");
fscanf(fp,"%d",&n);
int t,i,j;
memset(b,5,sizeof(b));
for(t=1;t<=n;t++)
fscanf(fp,"%d",&a[t]);
qs(1,n);
t1=n;
h1+=2;
t2++;
b[t2]=a[1]+a[2];
ans+=b[t2];
while(++num<n-1)
{
if(a[h1+1]<=b[h2]) {b[++t2]=a[h1]+a[h2]; ans+=b[t2]; h1+=2;}
else if(a[h1]>=b[h2+1]) {b[++t2]=b[h2]+b[h2+1];ans+=b[t2]; h2+=2;}
else {b[++t2]=a[h1++]+b[h2++]; ans+=b[t2];}
}
fp=fopen("fruit.out","w");
fprintf(fp,"%d",ans);
fclose(fp);
return 0;
}
⑨ 合并果子 C语言编程
先排序，然后从小到大合并，可以用贪心证明这是最优解