532 条题解
-
0badbkj LV 7 @ 2017-07-06 15:59:20
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<string>
#include<cstring>
using namespace std;
int ans,n,a[10005];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<n;i++)
{
int x;
x=a[i]+a[i+1];
ans+=x;
a[i+1]=x;
for(int j=i+2;j<=n;j++)
if(a[j]<a[j-1])swap(a[j],a[j-1]);
}
cout<<ans;
return 0;
} -
02017-07-06 15:51:02@
使用STL:
#include<iostream> #include<algorithm> #include<queue> using namespace std; int main() { priority_queue<int> q; int t; cin >> t; for(int i = 0; i < t; i++) { int in; cin >> in; q.push(-in); } int ans = 0; for(int i = 0; i < t - 1; i++) { int w = 0; w = q.top(); q.pop(); w += q.top(); q.pop(); ans += w; q.push(w); } cout << -ans << endl; return 0; }
-
02017-06-04 14:30:35@
#include<iostream> #include<string> #include<algorithm> #include<set> #include<vector> using namespace std; void calculate(vector<int>&s) { int consume = 0; int merge_first = 0; int merge_two = 0; int sum = 0; vector<int>::iterator it; while ((it = min_element(s.begin(), s.end())) != s.end()) { if (s.size() == 1) { printf("%d\n", sum); break; } if (it != s.end()) { merge_first = *it; s.erase(it); } it = min_element(s.begin(), s.end()); if (it != s.end()) { merge_two = *it; consume = merge_first + merge_two; sum += consume; s.erase(it); s.push_back(consume); } } } int main() { //freopen("data.in", "r", stdin); //freopen("data.out", "w", stdout); int n; int num; cin >> n; vector<int> s; for (int i = 0; i < n; i++) { cin >> num; s.push_back(num); } calculate(s); return 0; }
-
02017-05-31 17:35:19@
晕死,这么简单的题调了两天才发现时sort里的tot没有+2。。。
#include<cstdio> #include<algorithm> using namespace std; int n,a[100001]; long long p=0; void del(int& tot) { for(int i=1;i<=tot;i++) a[i]=a[i+1]; return; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); int tot=n-1; while(tot) { sort(a+1,a+tot+2); int sum=a[2]+a[1]; a[2]=sum; a[1]=0; p+=sum; del(tot); tot--; } printf("%lld",p); return 0; }
-
02017-05-26 12:56:46@
#include <cstdio>
#include <queue>
using namespace std;priority_queue<int,deque<int>,greater<int> > q;
int ans;inline int read(){
int f=1,s=0;
char c=getchar();
while(c<'0' || c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
s=s*10+c-'0';
c=getchar();
}
return f*s;
}int main(){
int n,i,a,b;
scanf("%d",&n);
for(i=1;i<=n;i++)
q.push(read());
for(i=1;i<n;i++){
a=q.top();
q.pop();
b=q.top();
q.pop();
ans+=a+b;
q.push(a+b);
}
printf("%d\n",ans);
return 0;
} -
02017-05-08 07:52:37@
经典的优先队列的问题
不多说咯#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <iomanip> #include <cstdlib> #include <queue> using namespace std; const int INF=0x7fffff; priority_queue<int,vector<int>,greater<int> > q; int n; long long ans=0; int main() { int a,b; int x; cin>>n; for(int i=1;i<=n;i++) cin>>x,q.push(x); for(int i=1;i<n;i++) { a=q.top();q.pop(); b=q.top();q.pop(); ans+=(a+b); q.push(a+b); } cout<<ans<<endl; return 0; }
-
02017-05-07 15:58:10@
STL模板题 priority_queue
(附压行代码)#include<bits/stdc++.h> using namespace std;priority_queue<int>q;int main(){int n,x;scanf("%d",&n);while(n--)scanf("%d",&x),q.push(-x);x=q.top();q.pop();n=0;while(!q.empty())n+=x+q.top(),q.push(x+q.top()),q.pop(),x=q.top(),q.pop();printf("%d",-n);}
-
02017-05-03 17:14:38@
Ac
#include<bits/stdc++.h>
using namespace std;
int n;
int a[10000];
void cut(int k)
{
for(int i=0;i<n-k;i++)a[i]=a[i+1];
}
int main()
{
int sum=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}int k=0;
while(k+1<n)
{sort(a,a+(n-k));
//for(int i=0;i<n-k;i++)cout<<a[i]<<" ";
//cout<<endl;
//cout<<"sum:"<<sum<<endl;
int s=a[0]+a[1];;
sum+=s;
a[1]=s;
cut(k);
k++;
}
cout<<sum<<endl;
return 0;
} -
02017-05-03 17:14:19@
#include<bits/stdc++.h>
using namespace std;
int n;
int a[10000];
void cut(int k)
{
for(int i=0;i<n-k;i++)a[i]=a[i+1];
}
int main()
{
int sum=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}int k=0;
while(k+1<n)
{sort(a,a+(n-k));
//for(int i=0;i<n-k;i++)cout<<a[i]<<" ";
//cout<<endl;
//cout<<"sum:"<<sum<<endl;
int s=a[0]+a[1];;
sum+=s;
a[1]=s;
cut(k);
k++;
}
cout<<sum<<endl;
return 0;
} -
02017-04-09 15:29:47@
#include "stdio.h"
int main()
{
int a[10000],n,min1,min0;
int t = 0;
scanf("%d",&n);
for(int e = 0; e < n; e++)
scanf("%d",&a[e]);
min0 = a[0] < a[1] ? 1 : 0;
min1 = a[0] >= a[1] ? 1 : 0;
int p = n;
while(p-1)
{
for(int q = 0; q < n; q++)
{
if(a[min0] > a[q] && a[min1] > a[q])
{
min0 = min1;
min1 = q;
}
else if(a[min0] > a[q] && a[min1] <= a[q] && min1 != q)
min0 = q;
}
a[min1] = a[min1] + a[min0];
t += a[min1];
a[min0] = 200000000;
p--;
}
printf("%d",t);
Sleep(25000);
return 0;
} -
02017-03-29 15:04:50@
优先队列!
#include<cstdio> #include<queue> using namespace std; priority_queue<int> data; int main() { int n; scanf("%d",&n); for(int i=1,x;i<=n;i++) { scanf("%d",&x); data.push(-x); } int res=0; for(int i=1,tmp;i<n;i++) { tmp=data.top(); res-=data.top(); data.pop(); tmp+=data.top(); res-=data.top(); data.pop(); data.push(tmp); } printf("%d",res); return 0; }
-
02017-03-19 23:33:05@
用priority_queue还是挺方便的
#include <iostream> #include <algorithm> #include <queue> #include <vector> using namespace std; int main() { priority_queue<int, vector<int>, greater<int>> fruits; int total; cin >> total; for (int i = 0; i < total; ++i){ int tmp; cin >> tmp; fruits.push(tmp); } int result = 0; while (fruits.size() != 1){ int tmp = fruits.top(); fruits.pop(); int tmp2 = fruits.top(); fruits.pop(); fruits.push(tmp + tmp2); result += tmp + tmp2; } cout << result << endl; return 0; }
-
02017-03-17 12:26:53@
没有必要对整个数组进行排序,只需单独考虑取前两位即可 #include <iostream> using namespace std; int n; int num[10000]; void change(int x) { int i,t,q; q=x; for (i=q+1;i<n;i++) { if (num[i]<num[q]) { q=i; } } t=num[x]; num[x]=num[q]; num[q]=t; } int main() { cin >> n; int i,j; int sum=0; for (i=0;i<n;i++) cin >> num[i]; change(0); change(1); for (i=1;i<n;i++) { num[i]+=num[i-1]; sum+=num[i]; change(i); change(i+1); } cout << sum; }
-
02017-03-11 10:27:49@
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;int n,i,a[10005],s;
int main()
{
cin>>n;
for(i=1; i<=n; ++i) cin>>a[i];
sort(a+1,a+n+1);
while(n>1)
{
a[1]=a[1]+a[2];
s=s+a[1];
for (i=3; i<=n; ++i) a[i-1]=a[i];
n=n-1;
sort(a+1,a+n+1);
}cout<<s;
return 0;
} -
02017-03-03 14:32:17@
将数组由小到大排序之后,每次都取前两个的和,按大小插入到剩下的数组中,保证剩下的数组也是从小到达排序的。
注意的是每次取和之后剩下数组的起始位置就往后挪一位。
java代码:
import java.util.*;
import java.io.*;
public class tanxin {
public static void main(String[]args)throws IOException{
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[]s=new int[n];
int temp,j,sum=0;
for(int i=0;i<n;i++)
s[i]=input.nextInt();
if(n==1)
{
System.out.println(s[0]);
return;
}Arrays.sort(s); //
for(int i=0;i<n-1;i++)
{
temp=s[i]+s[i+1];
sum+=temp;
for( j=i+1;j<n;j++)
{
if(s[j]<=temp)
s[j-1]=s[j];
else
break;
}
s[j-1]=temp;}
System.out.println(sum);
}
} -
02017-02-27 20:34:00@
#include <iostream> #include <cstring> #include <algorithm> #include <queue> using namespace std; int N,max_num,times=0; priority_queue<int, vector<int>, greater<int> > q; int main(){ int temp1,temp2,temp_sum,sum=0; cin>>N; for(int i = 1 ; i<=N ; i++){ cin>>temp1; q.push(temp1); } while(!q.empty()){ temp1=q.top(); q.pop(); if(q.empty()){ break; } temp2=q.top(); q.pop(); temp_sum=temp1+temp2; sum+=temp_sum; q.push(temp_sum); } cout<<sum<<endl; return 0; }
-
02017-02-20 21:22:25@
贪心,使用优先队列,每次从队列中拿出2个最小的,ans累加其和,再把和作为新的元素放入队列中,直到队列长度为1.
代码如下:
```c++#include <iostream>
#include <queue>using namespace std;
int main(void)
{
long long ans = 0;
priority_queue<int,vector<int>,greater<int> > p;
int n,i,a;
cin>>n;for(i = 0;i < n;i++){
cin>>a;
p.push(a);
}while(p.size() > 1){
int m1,m2;
m1 = p.top();
p.pop();
m2 = p.top();
p.pop();ans += m1 + m2;
p.push(m1 + m2);
}cout<<ans;
return 0;
} -
02017-01-18 10:14:18@
program fruit; const maxn=10002; var a:array[0..maxn]of longint; t,i,ans,n,sum:longint; procedure change(i,j:longint); var t:longint; begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; procedure up(i:longint); var tip:longint; begin if i=1 then exit; tip:=i div 2; if a[tip]>a[i] then begin change(i,tip); up(tip); end; end; procedure down(i:longint); var tip:longint; begin if i*2>n then exit; tip:=i*2; if (tip+1<n)and(a[tip]>a[tip+1]) then inc(tip); if (a[tip]<a[i]) then begin change(i,tip); down(tip); end; end; begin assign(input,'fruit.in');reset(input); readln(n); fillchar(a,sizeof(a),0); for i:=1 to n do begin read(a[i]); up(i); end; ans:=0; sum:=0; while n>1 do begin sum:=a[1];change(1,n);dec(n);down(1); inc(sum,a[1]);change(1,n);dec(n);down(1); inc(n); a[n]:=sum; up(n); inc(ans,sum); end; writeln(ans); close(input); end.```
-
02016-11-22 19:01:57@
测试数据 #0: Accepted, time = 15 ms, mem = 708 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 560 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 600 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 640 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 708 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 708 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 708 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 708 KiB, score = 10
Accepted, time = 90 ms, mem = 708 KiB, score = 100
代码
```C++
#include <iostream>
#include <cmath>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <climits>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>using namespace std;
int main()
{
int n;
cin>>n;priority_queue<int, vector<int>, greater<int>> ss;
int x;
for(int i=1;i<=n;i++)
{
cin>>x;
ss.push(x);
}int sum=0;
for(int i=1; i<=n-1; i++)
{
int uu=ss.top();
ss.pop();
int vv=ss.top();
ss.pop();
ss.push(uu+vv);
sum+=(uu+vv);
}cout<<sum;
return 0;
}
```
优先队列 每次都把优先级最高(果子数目最小)的合并起来 变成新的一个数据 放进队列 -
02016-11-20 20:59:09@
好心的我
#include<iostream>
#include<cstdio>
using namespace std;
int heap_size,n;
int heap[30001];
void swap(int &a,int &b)
{
int t=a;
a=b;
b=t;
}
void put(int d)
{
int now,next;
heap[++heap_size]=d;
now=heap_size;
while(now>1)
{
next=now>>1;
if(heap[now]>=heap[next])
return;
swap(heap[now],heap[next]);
now=next;
}
}
int get()
{
int now,next,res;
res=heap[1];
heap[1]=heap[heap_size--];
now=1;
while(now*2<=heap_size)
{
next=now*2;
if(next<heap_size&&heap[next+1]<heap[next])
next++;
if(heap[now]<=heap[next])
return res;
swap(heap[now],heap[next]);
now=next;
}
return res;
}
void work()
{
int i,x,y,ans=0;
cin>>n;
for(i=1;i<=n;++i)
{
cin>>x;
put(x);
}
for(i=1;i<n;++i)
{
x=get();
y=get();
ans+=x+y;
put(x+y);
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
work();
return 0;
}