535 条题解
-
0
yyyz108 LV 8 @ 2017-11-03 16:09:35
#include<bits/stdc++.h>
using namespace std;
int n,ans,k,maxn;
int num[10008],sum[10008];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>num[i];
num[n+1]=0;
sort(num+1,num+1+n);
while(1)
{
int flag=0;
ans=num[1]+num[2];
sum[k]=ans;
if(k==n-1)
{
for(int i=0;i<k;i++)
maxn+=sum[i];
cout<<maxn;
return 0;
}
for(int i=3;i<=n-k;i++)
{
if(ans>num[i])
num[i-2]=num[i];
else
{
flag=1;
num[i-2]=ans;
for(int j=i-1;j<=n-k;j++)
num[j]=num[j+1];
break;
}
}
if(!flag) num[n-k-1]=ans;
k++;
}
return 0;
} -
0
没看到有dalao发优先队列，我就补一个优先队列的做法 (｡˘•ε•˘｡)
（还有，这题直接sort会TLE……）#include<iostream> #include<queue> using namespace std; priority_queue<int,vector<int>,greater<int> >q; int n,x,ans=0,tmp=0; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>x; q.push(x); } for(int i=1;i<=n-1;i++) { tmp=q.top(); q.pop(); tmp=tmp+q.top(); q.pop(); q.push(tmp); ans=ans+tmp; } cout<<ans; return 0; } -
0
2351599120 LV 9 @ 2017-10-28 08:16:32
数组模拟队列
#include<bits/stdc++.h> using namespace std; int a[20001],b[20001]; int main() { int n,al=1,bl=1,br=1,ans=0; memset(a,0x3f,sizeof(a)); memset(b,0x3f,sizeof(b)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } sort(a+1,a+n+1); for(int i=1;i<n;i++) { if(a[al+1]<=b[bl]&&a[al]+a[al+1]<=b[bl]+b[bl+1]) { b[br]=a[al]+a[al+1]; ans+=b[br]; al+=2; br++; } else if(a[al+1]>=b[bl]&&a[al]<=b[bl+1]) { b[br]=a[al]+b[bl]; ans+=b[br]; al++; bl++; br++; } else { b[br]=b[bl]+b[bl+1]; ans+=b[br]; bl+=2; br++; } } printf("%d",ans); return 0; } -
0
很水的题
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
int a[20001],t=1;
using namespace std;
int main()
{
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
while(n-1>=t)
{
ans=ans+a[t]+a[t+1];
a[t+1]=a[t]+a[t+1];
t++;
sort(a+t,a+n+1);
}
printf("%d",ans);
} -
0
Binary_Heap LV 5 @ 2017-10-14 10:23:19
#include <iostream> #include <queue> using namespace std; priority_queue<int, vector<int>, greater<int> > a; int n, LQ; int t; int main() { int x, y; cin >> n; for(int i=1; i<=n; i++) { cin >> t; a.push(t); } for(int i=1; i<=n-1; i++) { x=a.top(); a.pop(); y=a.top(); a.pop(); a.push(x+y); LQ += x+y; } cout << LQ << endl; return 0; } -
0
#include <iostream>
#include <queue>
using namespace std;priority_queue<int, vector<int>, greater<int> > a;
int n, LQ;
int t;int main() {
int x, y;
cin >> n;
for(int i=1; i<=n; i++) {
cin >> t;
a.push(t);
}
for(int i=1; i<=n-1; i++) {
x=a.top();
a.pop();
y=a.top();
a.pop();
a.push(x+y);
LQ += x+y;
}
cout << LQ << endl;
return 0;
} -
0
var
s:array[0..10000]of longint;
i,j,n,m,v,t:longint;
begin
readln(n);
for i:=1 to n do
read(s[i]);
t:=0;
s[0]:=2147483647;
for i:=n downto 2 do
begin
m:=0;
for j:=1 to i do
if s[j]<s[m] then m:=j;
v:=s[i];
s[i]:=s[m];
s[m]:=v;
for j:=1 to i-1 do
if s[j]<s[m] then m:=j;
v:=s[i-1];
s[i-1]:=s[m];
s[m]:=v;
s[i-1]:=s[i-1]+s[i];
t:=t+s[i-1];
end;
write(t);
end. -
0
采用这个bisect.insort，保持有序序列的有序，不用每次都重新排序。省下来排序的时间。AC
import bisect series = int(input()) nums = list(map(int,(input().split())[:series])) total = 0 if series ==1: print(0) elif series == 2: print(sum(nums)) elif series > 2: nums.sort() while True: min2sum=nums[0]+nums[1] nums = nums[2:] bisect.insort(nums,min2sum) total += min2sum if len(nums) == 2: total += sum(nums) print(total) break -
0
Galileonardo LV 7 @ 2017-10-04 12:31:30
每一次合并前两项插入数组整体移动，注意项数变化及非0条件。
#include <iostream>
#include <algorithm>
using namespace std;int n,temp;
int arr[10005];
int ans=0;int main() {
cin>>n;
for(int i=0;i<n;i++){
cin>>arr[i];
}
sort(arr+0,arr+n);
for(int i=1;i<n;i++){
temp=arr[0]+arr[1];
//cout<<temp<<endl<<endl;
ans=ans+temp;
for(int j=2;arr[j]!=0;j++){
arr[j-2]=arr[j];
}
arr[n-i-1]=0;arr[n-i]=0;
//n-i+1个数 0到n-i
int j=0;
while((arr[j]<temp)&&(arr[j]!=0)){
j++;
}
for(int k=n-i-2;k>=j;k--){
arr[k+1]=arr[k];
}
arr[j]=temp;
/*for(int k=0;k<=n-i-1;k++){
cout<<arr[k]<<' ';
}cout<<endl<<endl;*/
}
cout<<ans;
return 0;
} -
0
无脑ac
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int a[10001];
int n;
int strength=0;
int num=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n-1;i++)
{
num=a[i]+a[i+1];
a[i+1]=num;
strength+=num;
sort(a+i+1,a+n+1);}
cout<<strength;
return 0;
} -
0
westfallon LV 8 @ 2017-09-15 16:57:56
想体验一下链表的妙处，于是尝试用链表写了下
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; struct node { int date; struct node *next; } ; int n,ans=0; struct node *head; void charu (int x) { if(x<head->date) { struct node *p; p=(struct node *)malloc(sizeof(struct node)); p->date=x; p->next=head; head=p; } else { struct node *t; t=head; while(t!=NULL) { if(t->next==NULL||t->next->date>x) { struct node *p; p=(struct node *)malloc(sizeof(struct node)); p->date=x; p->next=t->next; t->next=p; break; } t=t->next; } } } int main() { cin>>n; head=NULL; for(int i=1;i<=n;i++) { int a; cin>>a; if(head==NULL) { struct node *p; p=(struct node *)malloc(sizeof(struct node)); p->date=a; p->next=NULL; head=p; } else charu(a); } /* int t=n-1; for(int i=1;i<=t;i++) { int x,y,he; x=head->date; y=head->next->date; he=x+y; ans+=he; head=head->next->next; charu(he); }*/ int x,y,he=0; while(head!=NULL&&head->next!=NULL) { x=head->date; y=head->next->date; he=x+y; ans+=he; charu(he); head=head->next->next; } cout<<ans<<endl; /* struct node *t; t=head; while(t!=NULL) { cout<<t->date<<" "; t=t->next; }*/ return 0; } -
0
DinnerHunt LV 7 @ 2017-09-14 16:42:58
贪心算法 每次取最小值，合为新值，优先队列
//Vijos 1097 合并果子 #include <cstdio> #include <queue> using namespace std; const int maxn = 10000+10; int main(){ int number,n,sum=0; priority_queue<int,vector<int>,greater<int> > pq; scanf("%d",&number); for(int i=0;i<number;i++){ scanf("%d",&n); qp.push(n); } while(!pq.empty()){ int a=pq.top(); pq.pop(); if(pq.empty()) break; int b=pq.top(); pq.pop(); sum=sum+a+b; pq.push(a+b); } printf("%d",sum); return 0; } -
0
当然是优先队列啦
STL 大法好实际上是把 优先队列中**最小**的\(p_1\), \(p_2\)取出求和, 并且 \(ans += p_1 + p_2\), 然后将\(p_1 + p_2\)继续插入队列中
#include <iostream> #include <string> #include <queue> #include <vector> #include <functional> using namespace std; typedef unsigned long long ll; priority_queue<ll, vector<int>, greater<int> > pq; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { int t; cin >> t; pq.push(t); } ll ans = 0; while(!pq.empty()) { ll p1, p2; p1 = pq.top(); pq.pop(); p2 = pq.top(); pq.pop(); if (!pq.empty()) pq.push(p1 + p2); ans += p1 + p2; } cout << ans << endl; return 0; } -
0
zhuzihan031115 LV 7 @ 2017-08-29 21:29:10
var
a:array[1..10000] of longint;
n,i,c,d,ans:longint;procedure swap(x,y:longint);//交换函数
var
t:longint;
begin
t:=a[x]; a[x]:=a[y]; a[y]:=t;
end;function min(x,y:longint):longint;//找最小值
begin
if(a[x]>a[y]) then exit(y)
else
exit(x);
end;procedure down(x:longint);//将当前元素按堆的性质向下调整。
var
t:longint;
begin
t:=2*x;
while(t<=n)do
begin
if(t+1<=n) then
begin
t:=min(t,t+1);
if(a[x]>a[t]) then swap(x,t);
end
else
if(a[x]>a[t]) then swap(x,t);
x:=t; t:=2*x;
end;
end;procedure up(x:longint);//将当前元素按堆的性质向上调整。
var
t:longint;
begin
t:=x div 2;
while(t>0)do
begin
if(a[x]<a[t]) then
swap(x,t)
else
break;
x:=t;
t:=x div 2;
end;
end;procedure del;//删除最后一个节点（因为用过的节点放在最后）
begin
swap(1,n);
dec(n);
down(1);
end;procedure init(x:longint);//计算结果的步骤。
begin
inc(n);
ans:=ans+x;
a[n]:=x;
up(n);
end;begin
ans:=0;
readln(n);
for i:=1 to n do//读入
read(a[i]);
for i:=2 to n do//建堆
up(i);
while(n<>1)do
begin
c:=a[1];
del;
d:=a[1];
del;
init(c+d);
end;
writeln(ans);
end. -
0
yemaster (yemaster) LV 7 @ 2017-08-24 21:01:07
状态 题目 递交者 时间 内存 语言 递交时间
Accepted
P1097 合并果子 yemaster 38ms 256.0 KiB Pascal 39秒前
Accepted
/usr/bin/ld.bfd: warning: /out/link.res contains output sections; did you forget -T?状态 耗时 内存占用
#1 Accepted 4ms 256.0 KiB
#2 Accepted 1ms 256.0 KiB
#3 Accepted 1ms 256.0 KiB
#4 Accepted 2ms 256.0 KiB
#5 Accepted 4ms 256.0 KiB
#6 Accepted 3ms 256.0 KiB
#7 Accepted 5ms 256.0 KiB
#8 Accepted 5ms 256.0 KiB
#9 Accepted 5ms 256.0 KiB
#10 Accepted 4ms 256.0 KiB代码
我用的是单调队列
var a,b:array[0..30000] of longint; taila,heada,tailb,headb,x,y,i,n,sum:longint; function getmin:longint; begin //writeln('heada=',heada,' taila=',taila,' a[',heada,']=',a[heada]); //writeln('headb=',headb,' tailb=',tailb,' b[',headb,']=',a[headb]); if (heada<=taila) and (headb<=tailb) then begin if a[heada]<b[headb] then begin inc(heada); exit(a[heada-1]); end else begin inc(headb); exit(b[headb-1]); end; end else begin if heada<=taila then begin inc(heada); exit(a[heada-1]); end; inc(headb); exit(b[headb-1]); end; end; procedure qsort(l,r:longint); var i,j,m,t:longint; begin i:=l;j:=r; m:=a[(l+r) div 2]; repeat while a[i]<m do inc(i); while a[j]>m do dec(j); if I<=j then begin t:=a[i];a[i]:=a[j];a[j]:=t; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; begin readln(n); heada:=1;taila:=0; for i:=1 to n do begin inc(taila); read(a[taila]); end; qsort(1,n); headb:=1; for i:=1 to n-1 do begin x:=getmin; y:=getmin; //writeln('x=',x,' y=',y); inc(tailb); b[tailb]:=x+y; sum:=sum+x+y; end; writeln(sum); end. -
0
贪心、哈夫曼树的原理
用优先队列写出来很漂亮#include <iostream> #include <queue> #include <vector> using namespace std; bool cmp(int x,int y){ return x>y; } int main(){ priority_queue<int,std::vector<int>,greater<int> >q; int n; cin>>n; int x; int x1,x2; while(n--){ cin>>x; q.push(x); } int sum=0; while(q.size()>1){ x1=q.top(); q.pop(); x2=q.top(); q.pop(); sum+=x1+x2; q.push(x1+x2); } cout<<sum<<endl; return 0; } -
0
史上最简单
用STL中的**堆**，方便快捷！！！#include<bits/stdc++.h> using namespace std; int n,ans,num,s; priority_queue<int,vector<int>,greater<int> >pq; int main() { ans=0; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&num); pq.push(num); } for (int i=1;i<n;i++) { s=0; s+=pq.top(); pq.pop(); s+=pq.top(); pq.pop(); ans+=s; pq.push(s); } printf("%d",ans); return 0; } -
0
Accepted++ LV 8 @ 2017-08-04 16:31:58
/*
NOIP2004提高组 T2
直接贪心复杂度O(N^2)，优先队列复杂度O(NlogN)，使用单调队列除排序复杂度O(N)。
单调队列思想：a数组存放排序后的果子，每次从a,b队头（如果元素数量不为0）拿出2个最小的元素合并，合并后结果存入b数组。
*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e4;
int a[MAXN],b[MAXN]={};
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;++i) scanf("%d",a+i);
sort(a,a+n);
int af=0,bf=0; //af是队列a队头,bf是队列b队头
for(int br=0;br<n-1;++br){ //b[br]存储本次合并新的一堆果子数量（也是合并花费的体力）
if(af==n){b[br]=b[bf]+b[bf+1]; bf+=2; continue;} //队列a中没有元素
if(bf==br){b[br]=a[af]+a[af+1]; af+=2; continue;} //队列b中没有元素
if(af+1==n){ //队列a中只有1个元素
if(bf+1==br) b[br]=a[af]+b[bf];
else if(b[++bf]<a[af]) b[br]=b[bf-1]+b[bf++];
else b[br]=a[af++]+b[bf-1];
continue;
}
if(bf+1==br){ //队列b中只有1个元素
if(af+1==n) b[br]=a[af]+b[bf];
else if(a[++af]<b[bf]) b[br]=a[af-1]+a[af++];
else b[br]=b[bf++]+a[af-1];
continue;
}
for(int j=0;j<2;++j){ //队列a,b中都至少有2个元素
if(a[af]<b[bf]) b[br]+=a[af++];
else b[br]+=b[bf++];
}
}
int ans=0;
for(int i=0;i<n-1;++i) ans+=b[i];
printf("%d",ans);
return 0;
} -
0
不知道有木有人也用stl的优先队列
cpp
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int main ()
{
priority_queue<int,vector<int>,greater<int> > pq;
int n,x,sum=0;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x;
pq.push(x);
}
x=0;
while(pq.size()>1)
{
x+=pq.top();pq.pop();
x+=pq.top();pq.pop();
sum+=x;pq.push(x);
x=0;
}
cout<<sum;
return 0;
}
-
0
STL 大法好~~~
#include<bits/stdc++.h> using namespace std; bool compare(int a,int b) { return a>b; } int main() { int i,n,sum=0,a[10005]; cin>>n; for(i=0;i<n;i++) cin>>a[i]; make_heap(a,a+n,compare); sum=0; for(i=n;i>1;i--) { pop_heap(a,a+i,compare); pop_heap(a,a+i-1,compare); a[i-2]+=a[i-1]; sum+=a[i-2]; push_heap(a,a+i-1,compare); } cout<<sum; return 0; }
yyyz108
LV 8
@ 2017-11-03 16:09:35
