532 条题解
-
0
cjoier_gjh LV 8 @ 2016-11-18 14:08:36
这题很简单！queue
#include<stdio.h>
#include<stdlib.h>
#include<queue>
using namespace std;
priority_queue<int>que;
int main(){
int n;
scanf("%d",&n);
for(int i=0,x;i<n;i++){
scanf("%d",&x);
que.push(-x);
}
int ans=0;
for(int i=1,tmp;i<n;i++){
tmp=que.top();
ans-=que.top();
que.pop();
tmp+=que.top();
ans-=que.top();
que.pop();
que.push(tmp);
}
printf("%d\n",ans);
return 0;
} -
0
这是优化过了的C （在电脑无法编译及运行下强行记事本（@——@）
#include<stdio.h>int main()
{
int n,i,m,j,t,k,ans=0,a[9999999],x,y;
scanf("%d",&n);
m=n;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}while(m>1)
{
if(m==2)
{
ans=ans+a[1]+a[2];
printf("%d",ans);
return 0;
}
x=a[1];
for(i=2;i<=m;i++)
{
if(a[i]<x)
{
t=a[i];
a[i]=x;
x=t;
}
}
a[1]=x;y=a[2];
for(i=3;i<=m;i++)
{
if(a[i]<y)
{
t=a[i];
a[i]=y;
y=t;
}
}
a[2]=y;ans=ans+a[1]+a[2];
a[1]=a[1]+a[2];
for(i=2;i<m;i++)
{
a[i]=a[i+1];
}
m--;}
return 0;
} -
0
为什么用sort函数只得一半而手打快排就得满了？
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int x,int y)
{
return x<y;
}
int main()
{
int n,i,j,count=0,a[10001];
cin>>n;
for(i=0;i<n;++i)
cin>>a[i];
sort(a,a+n-1,cmp);
for(i=0;i<n-1;++i)
{
count+=a[i]+a[i+1];
a[i+1]=a[i]+a[i+1];
a[i]=0;
for(j=i+1;j<n-1;++j)
if (a[j]>a[j + 1])
swap(a[j],a[j + 1]);
else break;
}
cout<<count;
return 0;
} -
0
#include <bits/stdc++.h> using namespace std; int n,i,a,b,ans; priority_queue<int,vector<int>,greater<int> >q; int main() { cin>>n; for (i=1; i<=n; i++) { cin>>a; q.push(a); } while (q.size()>1) { a=q.top(); q.pop(); b=q.top(); q.pop(); ans+=a+b; q.push(a+b); } cout<<ans<<endl; } -
0
注意优先队列默认是大的优先，greater是小的优先，less是大的优先
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;int main(){
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int t;
scanf("%d",&t);
q.push(t);
}
for(int i=1;i<=n-1;i++){
int p1=q.top();
q.pop();
int p2=q.top();
q.pop();
int t=p1+p2;
ans+=t;
q.push(t);
}
printf("%d",ans);
return 0;
}-
lambdacat @ 2016-11-10 15:27:59
Yes，踩到这个坑了，用自己的数据调了半天发现结果很诡异，然后怒输出中间状态后恍然大悟
-
-
0
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;long long a[10005];
int main() {
int n;
scanf("%d", &n);
for (int i=1;i <= n;i++) {
scanf("%d", &a[i]);
}
sort(a+1, a+n+1);long long ans=0;
for (int i=2;i <= n;i++) {
a[i]+=a[i-1];
ans+=a[i];
int k=i;
while (a[k] > a[k+1] && k+1 <= n) {
int t=a[k];
a[k]=a[k+1];
a[k+1]=t;
k++;
}
}printf("%d", ans);
return 0;
}每次迭代更新，将刚计算出的值更新到递增序列中合适的位置。
数学归纳法证明，不妨设有三个数（两个数则无需证明，直接合并）：a<b<c，则有三种合并方式a+b+a+b+c,a+c+a+b+c,
b+c+a+b+c，注意到最后三项均为a+b+c，又因为a<b<c，所以三项中最小的是第一个，即先选最小的a，b合并，再与c合并。当又有一项d时可以先选择两项合并，就退化成三项（将合并后的一项看成新的一项）的情况了， 则由数学归纳法就可证明成立。 -
0
评测结果
编译成功Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
Linking foo.exe
57 lines compiled, 0.0 sec, 27856 bytes code, 1268 bytes data
测试数据 #0: Accepted, time = 15 ms, mem = 888 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 892 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 888 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 888 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 884 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 888 KiB, score = 10
Accepted, time = 45 ms, mem = 892 KiB, score = 100
代码
```pascal
var heap:array[0..20001] of longint;
n,i,t,len,a,ans:longint;//function min(a,b:longint):longint;
//begin if a>b then exit(b);exit(a);end;procedure swap(var a,b:longint);
var t:longint;
begin t:=a;a:=b;b:=t;end;procedure put(a:longint);
var i:longint;
begin
inc(len);
heap[len]:=a;
i:=len;
while (heap[i]<heap[i>>1])and(i<>1) do begin
swap(heap[i],heap[i>>1]);
i:=i>>1;
end;
end;function get:longint;
var i,t:longint;
begin
get:=heap[1];
heap[1]:=heap[len];
heap[len]:=maxlongint;
dec(len);i:=1;
if len=0 then exit;
while true do begin
t:=i<<1;
if (heap[i]>heap[t])and(heap[t]<heap[t+1])then begin
swap(heap[i],heap[t]);i:=t;end
else if (heap[i]>heap[t+1])then begin
swap(heap[i],heap[t+1]);i:=t+1;end
else break;
end;
end;begin
readln(n);
filldword(heap,length(heap),maxlongint);
//writeln(heap[1]);
len:=0;
for i:=1 to n do begin
read(t);
put(t);
end;
ans:=0;//for i:=1 to len do write(heap[i],' ');writeln;
while len>1 do begin
a:=get+get;
inc(ans,a);
put(a);
//for i:=1 to len do write(heap[i],' ');writeln;
end;
writeln(ans);
end.
``` -
0
var n,i,s:longint; a:array[0..11111] of longint; procedure qsort(l,r:longint); var i,j,x,p:longint; begin i:=l; j:=r; x:=random(j-i+1)+i; p:=a[x]; repeat while a[i]>p do inc(i); while a[j]<p do dec(j); if i<=j then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if j>l then qsort(l,j); end; procedure insort(i:longint); var h:longint; begin a[0]:=a[i]; h:=i-1; while a[0]>a[h] do begin a[h+1]:=a[h]; dec(h); end; a[h+1]:=a[0]; end; begin randomize; readln(n); for i:=1 to n do read(a[i]); readln; qsort(1,n); for i:=n-1 downto 1 do begin a[i]:=a[i+1]+a[i]; s:=s+a[i]; insort(i); end; writeln(s); readln; end. -
0
#include<iostream> #include<algorithm> using namespace std; const int N=30005; int n,a[N],ans(0); void adjust(int i,int k){ int j=2*i+1; while(j<=k){ if(j<=k){ if(j<k&&a[j]>a[j+1])j++; if(a[i]>a[j]){ swap(a[i],a[j]); i=j; j=2*i+1; } else break; } } } void heapsort(int n){/*将二叉树调整成小顶堆*/ for(int i=(n-2)/2;i>=0;i--)adjust(i,n-1); for(int i=n-1;i>0;i--){ swap(a[0],a[i]); adjust(0,i-1); a[0]+=a[i];ans+=a[0]; adjust(0,i-1); } } int main(){ cin>>n; for(int i=0;i<n;i++)cin>>a[i]; heapsort(n); cout<<ans<<endl; return 0; } -
0
#include <iostream> #include <algorithm> using namespace std; int f[60007]; int main() { int n, i; cin >> n; for (i = 1; i <= n; i++) cin >> f[i]; int m = (n << 1) - 1, Res = 0, t1 = 1, t2 = n + 1, t, s[2] = {0}; sort(f + 1, f + n + 1); for (i = n + 1; i <= m; i++) { for (t = 0; t < 2; t++) if ((t2 < i && f[t2] < f[t1]) || t1 > n) s[t] = f[t2++]; else s[t] = f[t1++]; Res += (f[i] = s[0] + s[1]); } cout << Res << endl; return 0; } -
0
#include<iostream> #include<algorithm> using namespace std; const int N=30005; int n,a[N],ans(0); int main(){ cin>>n; for(int i=0;i<n;i++)cin>>a[i]; make_heap(a,a+n,greater<int>()); for(int i=n-1;i>0;i--){ pop_heap(a,a+i+1,greater<int>()); pop_heap(a,a+i,greater<int>()); a[i-1]+=a[i]; ans+=a[i-1]; push_heap(a,a+i,greater<int>()); } cout<<ans<<endl; return 0; } -
0
JerryZheng LV 8 @ 2016-10-07 16:13:36
//fruit
//2016-10-06 Shanghaineese Eccentric
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int> que;
int n,sum;int main()
{
int a,b,i,temp;
// freopen("fruit2.in","r",stdin);
// freopen("fruit.out","w",stdout);
sum=0;
scanf("%d",&n);
for (i=0;i<n;i++)
{
scanf("%d",&temp);
que.push(-temp);
}
while (que.size()>=2)
{
a=que.top();
que.pop();
b=que.top();
que.pop();
sum+=a+b;
que.push(a+b);
}
cout<<-sum<<endl;
return(0);
} -
0
#include <iostream>
using namespace std;
int apple[10000];
void ksort(int l, int r)//快排
{
if (l == r)return;
int mid = apple[(l + r) / 2];
int i = l, j = r;
int temp;
do
{
while (apple[i] < mid)i++;
while (mid < apple[j])j--;
if (i <= j)
{
temp = apple[i];
apple[i] = apple[j];
apple[j] = temp;
i++;
j--;
}
} while (i <= j);
if (i <= r)ksort(i, r);
if (l <= j)ksort(l, j);
return;
}int main()
{
int ans = 0;//花费力气
int n;//堆数
int i, j;
cin >> n;
for (i = 0; i < n; ++i)
cin >> apple[i];
ksort(0, n - 1);
for (i = 0; i < n-1; ++i)
{
ans += apple[i] + apple[i + 1];
apple[i + 1] = apple[i] + apple[i + 1];
apple[i] = 0;
for (j = i + 1; j < n - 1; ++j)
if (apple[j] > apple[j + 1])swap(apple[j], apple[j + 1]);
else break;
}
cout << ans;
system("pause");
return 0;
} -
0
#include <iostream>
using namespace std;
int apple[10000];
void ksort(int l, int r)//快排
{
if (l == r)return;
int mid = apple[(l + r) / 2];
int i = l, j = r;
int temp;
do
{
while (apple[i] < mid)i++;
while (mid < apple[j])j--;
if (i <= j)
{
temp = apple[i];
apple[i] = apple[j];
apple[j] = temp;
i++;
j--;
}
} while (i <= j);
if (i <= r)ksort(i, r);
if (l <= j)ksort(l, j);
return;
}int main()
{
int ans = 0;//花费力气
int n;//堆数
int i, j;
cin >> n;
for (i = 0; i < n; ++i)
cin >> apple[i];
ksort(0, n - 1);
for (i = 0; i < n-1; ++i)
{
ans += apple[i] + apple[i + 1];
apple[i + 1] = apple[i] + apple[i + 1];
apple[i] = 0;
for (j = i + 1; j < n - 1; ++j)
if (apple[j] > apple[j + 1])swap(apple[j], apple[j + 1]);
else break;
}
cout << ans;
system("pause");
return 0;
} -
0
#include<bits/stdc++.h> using namespace std; struct cmp1 { bool operator ()(int &a,int &b) { return a>b; } }; priority_queue<int,vector<int>,cmp1>x; int n,a,num=0,b; int main(){ freopen("hb.in","r",stdin); freopen("hb.out","w",stdout); scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a); x.push(a); } for( int j=0;j<n-1;j++){ a=x.top(); x.pop(); b=x.top(); x.pop(); x.push(a+b); num+=a+b; } cout<<num; return 0; } -
0
STL大法
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int a;
int n,l;
long long f1,f2,ans=0;
int input()
{
int x = 0;
int f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
struct cmp{
bool operator() (const int a,const int b) const{
return a > b;
}
};
priority_queue<int,vector<int>,cmp> q;
int main()
{
n=input();
for(int i=1;i<=n;i++)
{
a=input();
q.push(a);
}
while(q.size()!=1)
{
f1=q.top();
q.pop();
f2=q.top();
q.pop();
ans+=f1+f2;
q.push(f1+f2);
}
cout<<ans;
return 0;
} -
0
#include"iostream"
#include"stdio.h"
#include"vector"
#include"functional"
#include"string"
#include"cstring"
#include"algorithm"
#include"queue"
#include"set"
#include"queue"
#define f1 cout<<"fuck1"<<endl;
#define f2 cout<<"fuck2"<<endl;#define f(x) (p*exp(-x)+q*sin(x)+r*cos(x)+s*tan(x)+t*x*x+u)
#define eps=1e-6
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
int main()
{
int n;
while(cin>>n)
{
priority_queue<int,vector<int>,greater<int> >Q;
int i;
for(i=0;i<n;i++)
{
int a;
scanf("%d",&a);
Q.push(a);
}
int ans=0;
while(Q.size()!=1)
{
int t1,t2;
t1=Q.top();Q.pop();t2=Q.top();Q.pop();
ans+=t1+t2;
Q.push(t1+t2);
}
cout<<ans<<endl;
}
} -
0
black_sky_zhang LV 9 @ 2016-08-24 20:42:02
用c++stl库就行啦
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
long long n,x,y,ans=0;
priority_queue<long long,vector<long long>,greater<long long> > h;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&x);
h.push(x);
}
for(int i=1;i<=n-1;i++)
{
x=h.top();h.pop();
y=h.top();h.pop();
ans+=x+y;h.push(x+y);
}
printf("%lld",ans);
return 0;
} -
0
program fruit;
var
a:array [1..10000] of longint;
i,m,n,x,j,total:longint;procedure QuickSort(low,high:longint);
var
i,j,mid,med:longint;
begin
i:=low;
j:=high;
mid:=a[(i+j) div 2];
repeat
while a[i]<mid do
i:=i+1;
while a[j]>mid do
j:=j-1;
if i<=j then
begin
med:=a[i];
a[i]:=a[j];
a[j]:=med;
i:=i+1;
j:=j-1;
end;
until i>j;
if i<high then QuickSort(i,high);
if j>low then QuickSort(low,j);
end;begin
readln(n);
for i:=1 to n do
read(a[i]);
QuickSort(1,n);
for i:=1 to n-1 do
begin
x:=a[i]+a[i+1];
a[i]:=0;
a[i+1]:=0;
total:=total+x;
j:=i+2;
while (j<=n) and (x>a[j]) do
j:=j+1;
j:=j-1;
for m:=i+1 to j do
a[m]:=a[m+1];
a[j]:=x;
end;
write(total);
end. -
0
shadowland LV 7 @ 2016-08-15 00:30:02
#include <bits/stdc++.h> #define maxN 100010 using namespace std; typedef long long QAQ ; int arr[maxN]; priority_queue<int ,vector<int>,greater<int> >Q; QAQ ans ; int main(){ int n,tmp2,tmp1; ios::sync_with_stdio(false); cin >> n ; for(int i=1 ; i<=n ;++i)cin >> arr[i]; sort(arr+1,arr+n+1); for(int i=1;i<=n;++i){ Q.push(arr[i]); } for(int i=1;i<=n-1;++i){ tmp1=Q.top(); Q.pop(); tmp2=Q.top(); Q.pop(); Q.push(tmp1+tmp2); ans+=tmp1+tmp2; } printf("%lld",ans); return 0 ; }
cjoier_gjh
LV 8
@ 2016-11-18 14:08:36
