很水的题

#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);
}

#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;
}

#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;
}

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.

采用这个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条件。
#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;
}

无脑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;
}

想体验一下链表的妙处，于是尝试用链表写了下

#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;
}

贪心算法 每次取最小值，合为新值，优先队列

//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;
}

当然是优先队列啦 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;
}

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.

状态 题目 递交者 时间 内存 语言 递交时间
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.

贪心、哈夫曼树的原理
用优先队列写出来很漂亮

#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;
}

史上最简单
用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;
}

/*
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;
}

不知道有木有人也用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;
}


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;
}

我用了 C++17 ，然后 Compile Error

#include <iostream>
#include <queue>

int main([[maybe_unused]] int argc, [[maybe_unused]] const char *argv[])
{
  std::priority_queue<int, std::vector<int>, std::greater<>> stack;
  int num;
  std::cin >> num;
  for (int i = 0; i < num; ++i) {
    int tmp;
    std::cin >> tmp;
    stack.push(tmp);
  }
  num = 0;
  while(stack.size() > 1) {
    auto tmp = stack.top();
    stack.pop();
    tmp += stack.top();
    stack.pop();
    stack.push(tmp);
    num += tmp;
  }
  std::cout << num << std::endl;
}

var
a,b:array[1..215000000]of integer;
n,i,j,s,m,f:longint;
begin
readln(n);for i:=1 to n do begin read(a[i]);inc(b[a[i]]);end;
while n>1 do begin
f:=0;i:=1;m:=0;
while f<2 do begin
while b[i]>0 do begin inc(f);inc(s,i);inc(m,i);dec(b[i]);end;
inc(i);
end;
inc(b[m]);dec(n);
end;
writeln(s);
end.

双队列
var
a,b:array[1..10010] of longint;
n,i,ans,ha,hb,tb,ne:longint;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do
inc(i);
while x<a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
begin
readln(n);
for i:=1 to n+1 do
begin
a[i]:=maxlongint;
b[i]:=maxlongint;
end;
for i:=1 to n do
read(a[i]);
sort(1,n);
ha:=1;hb:=1;tb:=0;ans:=0;
for i:=1 to n-1 do
begin
ne:=0;
if a[ha]<=b[hb] then begin
ne:=ne+a[ha];
inc(ha);
end
else begin
ne:=ne+b[hb];
inc(hb);
end;
if a[ha]<=b[hb] then begin
ne:=ne+a[ha];
inc(ha);
end
else begin
ne:=ne+b[hb];
inc(hb);
end;
inc(tb);
b[tb]:=ne;
ans:=ans+ne;
end;
write(ans);
end.