合並果子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語言編程
先排序，然後從小到大合並，可以用貪心證明這是最優解