题解 - Vijos

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

腾腾~仙 LV 7 @ 2016-08-16 10:16:10

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

0

newer86 LV 6 @ 2016-08-13 15:05:20

！最小生成树+排序算法解决：
#include <iostream>
using namespace std;
void run(int*pData,int left,int right)
{
int i,j;
int middle,iTemp;
i=left;
j=right;
middle=pData[(left+right)/2];//求中间值
do
{
while((pData[i]<middle)&&(i<right))//从左扫描小于中值的数
i++;
while((pData[j]>middle)&&(j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp=pData[i];
pData[i]=pData[j];
pData[j]=iTemp;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）

//当左边部分有值(left<j)，递归左半边
if(left<j)
run(pData,left,j);
//当右边部分有值(right>i)，递归右半边
if(right>i)
run(pData,i,right);
}
void QuickSort(int*pData,int Count)
{
run(pData,0,Count-1);
}

int main()
{
int n,a[10000],i,j,k,t,is,sum=0;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
}
QuickSort(a,n);
for(i=0;i<n-1;i++)
{
sum+=a[i]+a[i+1];
a[i+1]=a[i]+a[i+1];
is=0;
for(j=i+2;j<n;j++)
{
if(a[j]>=a[i+1])
{
is=1;
t=a[i+1];
for(k=i+1;k<j-1;k++)a[k]=a[k+1];
a[j-1]=t;
break;
}
}
if(is==0)
{
t=a[i+1];
for(k=i+1;k<n-1;k++)a[k]=a[k+1];
a[n-1]=t;
}
}

cout<<sum<<endl;

return 0;
}

0

program543 LV 8 @ 2016-08-08 15:10:48

哈夫曼树
#include <stdio.h>
#include <string.h>
struct node
{
int father;
int weight;
int old;
};
node tree[100000];
int height(int h1)
{
if (tree[h1].father==-1) return 0;
return height(tree[h1].father)+1;
}
int main()
{
int n,tot;
scanf("%d",&n);
tot=n;
for (int i=1;i<=n;i++)
{
scanf("%d",&tree[i].weight);
tree[i].old=1;
}
for (int i=1;i<=2*n-1;i++)
tree[i].father=-1;
for (int i=1;i<=2*n-2;i++)
{
int p1=100000000;
int k1=0;
for (int j=1;j<=2*n-1;j++)
if (tree[j].father==-1 && tree[j].weight<p1 && tree[j].weight)
{
k1=j;
p1=tree[j].weight;
}
int p2=1000000000;
int k2=0;
for (int j=1;j<=2*n-1;j++)
if (tree[j].father==-1 && tree[j].weight<p2 && tree[j].weight && j!=k1)
{
k2=j;
p2=tree[j].weight;
}
if (!k1 || !k2) break;
int k3=0;

if (k3==0)
{
tot=tot+1;
k3=tot;
}
tree[k3].weight=tree[k2].weight+tree[k1].weight;
tree[k2].father=tree[k1].father=k3;
}
int add=0;
for (int i=1;i<=2*n-1;i++)
if (tree[i].old)
add=add+tree[i].weight*(height(i));
printf("%d",add);
return 0;
}

0

xuanc LV 6 @ 2016-07-26 06:55:08

紫书例题。。

#include<iostream>
#include<queue>

int main()
{
using namespace std;
int ans=0,n,o;
priority_queue<int,vector<int>,greater<int> >q;
cin>>n;
for(int i = 0; i < n; i++ ){
cin>>o;q.push(o);}
for(int i = 0;i < n-1 ; i++)
{
int a = q.top();q.pop();
int b = q.top();q.pop();
ans+=a+b;
q.push(a+b);
}
cout<<ans;
return 0;
}

0

caesar_199 LV 9 @ 2016-07-22 21:12:01

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;

int n;

int main ()
{
    priority_queue<int, vector<int>, greater<int> > Q;
    cin >> n;
    int T = n - 1;
    int x;
    while (n--) { cin >> x; Q.push(x);}
    int ans = 0;
    while (T--) {
        int w1 = Q.top(); Q.pop();
        int w2 = Q.top(); Q.pop();
        ans += w1 + w2;
        Q.push(w1+w2);
    }
    cout << ans << "\n";
    return 0;
}

0

15958607157 LV 7 @ 2016-07-22 21:00:09

var i,j,x,n,max:longint;
a:array[1..100000000] of longint;
flag:boolean;
ans:int64;
begin
ans:=0;max:=0;
readln(n);fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
read(x);
inc(a[x]);
max:=max+x;
end;
if max>100000000 then max:=100000000;
i:=1;
while i<=max do
begin
flag:=false;
if a[i]>=2 then
repeat
a[i]:=a[i]-2;
inc(a[2*i]);
ans:=ans+2*i;
until a[i]<2;
if a[i]=1 then
for j:=i+1 to max do
begin
if (a[i]>0) and (a[j]>0) then
begin
dec(a[i]);
dec(a[j]);
inc(a[i+j]);
ans:=ans+i+j;
flag:=true;
end;
if flag then break;
end;
inc(i);
end;
write(ans);

end.

0

芙兰朵露•斯卡雷特 LV 8 @ 2016-07-14 16:55:24

优先队列

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct data{
    int val;
    inline bool operator < (const data&data1) const{
        return data1.val<val;
    }
};
template<class T>
class PriorityQueue : public priority_queue<T>{
public:
    T pop (){
        T tmp=priority_queue<T>::top();
        priority_queue<T>::pop();
        return tmp;
    }
};
PriorityQueue <data> que;
int main(int argc, char const *argv[]){
    /* code */
    //freopen("165.in","r",stdin);
    //freopen("165.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n,ans=0;
    cin>>n;
    data tmp;
    for(int i=0;i<n;i++){
        cin>>tmp.val;
        que.push(tmp);
    }
    for(int i=1;i<n;i++){
        tmp=que.pop();
        tmp.val+=que.pop().val;
        ans+=tmp.val;
        que.push(tmp);
    }
    cout<<ans;
    return 0;
}

0

chronix LV 8 @ 2016-07-14 10:22:36

#include <cstdio>
#include <queue>

using std::priority_queue;
using std::vector;
using std::greater;

int main(){
int n,sum=0,t;
priority_queue<int,vector<int>,greater<int> > q;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&t);
q.push(t);
}
for(int i=1;i<=n-1;i++){
int a1=q.top();
q.pop();
int a2=q.top();
q.pop();
sum+=a1+a2;
q.push(a1+a2);
}
printf("%d",sum);
return 0;
}

0

另刂石欠木又寸 LV 8 @ 2016-07-10 13:32:13

测试数据 #0: Accepted, time = 140 ms, mem = 860 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 856 KiB, score = 10
测试数据 #4: Accepted, time = 31 ms, mem = 864 KiB, score = 10
测试数据 #5: Accepted, time = 31 ms, mem = 864 KiB, score = 10
测试数据 #6: Accepted, time = 125 ms, mem = 864 KiB, score = 10
测试数据 #7: Accepted, time = 125 ms, mem = 860 KiB, score = 10
测试数据 #8: Accepted, time = 125 ms, mem = 860 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 864 KiB, score = 10
Accepted, time = 717 ms, mem = 864 KiB, score = 100

var a:array[0..15000] of longint;
i,j,n,k,tem,sum:longint;

procedure init;
begin
readln(n);
for i:=1 to n do
read(a[i]);
end;

procedure qsort(left,right:integer);

var i,j,x,t:longint;
begin
i:=left; j:=right;
x:=a[i];
repeat
while (a[j]<x)and(i<j) do dec(j);
if i<j then
begin
t:=a[i]; a[i]:=a[j];a[j]:=t;inc(i);
end;
while (a[i]>x)and(j>i) do inc(i);
if i<j then
begin
t:=a[i]; a[i]:=a[j];a[j]:=t;dec(j);
end;
until i=j;
inc(i);dec(j);
if i<right then qsort(i,right);
if j>left then qsort(left,j);
end;

procedure work;
begin
sum:=0;
while n>=2 do
begin
tem:=a[n]+a[n-1];
sum:=sum+tem;
j:=1;
while a[j]>tem do j:=j+1;
for k:=n downto j do
a[k+1]:=a[k];
a[j]:=tem;
n:=n-1;
end;
end;

begin
init;
qsort(1,n);
work;
writeln(sum);
end.

0

1782847451 LV 6 @ 2016-06-24 10:38:28

#include<cstdio>
int heap[30001];
int n;
void swap(int &a,int &b){
int t=b;
b=a;
a=t;
}
int len;
void put(int val){
int now,next;
heap[++len]=val;
now=len;
while(now>1){
int next=now/2;
if(heap[next]<=heap[now]){
return;
}
else{
swap(heap[next],heap[now]);
now=next;
}
}
}
int get(){
int now,next,res;
res=heap[1];
heap[1]=heap[len--];
now=1;
while(now*2<=len){
next=now*2;
if(next<len&&heap[next]>heap[next+1]){
next++;
}
if(heap[now]<=heap[next]){
return res;
}
swap(heap[now],heap[next]);
now=next;
}
return res;
}
void work(){
int num,lum;
int sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&num);
put(num);
}
for(int i=1;i<n;i++){
num=get();
lum=get();
sum+=num+lum;
put(num+lum);
}
printf("%d\n",sum);
}
int main()
{
work();
return 0;
}

0

SSLZ-Michael LV 8 @ 2016-06-22 11:53:45

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int n,a[30001],tmp,n1,ans=0;
void shift(int r,int n)
{int v=a[r];
int k=2*r;
while(k<=n)
{
if((a[k]>a[k+1])&&k<n)
k++;
if(v<a[k])
break;
else
{a[r]=a[k];
r=k;
k=k*2;}
}
a[r]=v;
}
void jianli()
{int r;
for(r=n/2;r>=1;r--)
shift(r,n);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
jianli();
n1=n;
for(int i=1;i<=n-1;i++)
{
tmp=a[1];
a[1]=a[n1];
n1--;
shift(1,n1);
a[1]=tmp+a[1];
ans=ans+a[1];
shift(1,n1);
}
cout<<ans;
return 0;
}

0

Note LV 8 @ 2016-06-12 10:25:34

不是一个优先队列就没了吗= =时间也很优越啊。
难道你们都哪来练习哈弗曼树吗= =

0

waiwas LV 6 @ 2016-04-06 16:21:27

测试数据 #0: Accepted, time = 218 ms, mem = 880 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 880 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 880 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 884 KiB, score = 10

测试数据 #4: Accepted, time = 31 ms, mem = 880 KiB, score = 10

测试数据 #5: Accepted, time = 46 ms, mem = 880 KiB, score = 10

测试数据 #6: Accepted, time = 187 ms, mem = 880 KiB, score = 10

测试数据 #7: Accepted, time = 218 ms, mem = 884 KiB, score = 10

测试数据 #8: Accepted, time = 187 ms, mem = 880 KiB, score = 10

测试数据 #9: Accepted, time = 234 ms, mem = 880 KiB, score = 10

Accepted, time = 1136 ms, mem = 884 KiB, score = 100

program p1097;
var
a:array[1..20000] of longint;
i,n,j,y,m,ans,x:longint;
procedure qsort(l,r:longint);
var i,j,mid,p:longint;
begin
i:=l;j:=r;
mid:=a[(l+r) div 2];
repeat
while a[i]<mid do
i:=i+1;
while a[j]>mid do
j:=j-1;
if i<=j then
begin
p:=a[i];a[i]:=a[j];a[j]:=p;
i:=i+1;
j:=j-1;
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
begin
ans:=0;
readln(n);
for i:=1 to n do
read(a[i]);
qsort(1,n);
for i:=1 to n-1 do
begin
x:=a[i]+a[i+1];
ans:=ans+x;
a[i+1]:=x;
for j:=i+1 to n-1 do
begin
if a[j]>a[j+1] then
begin
m:=a[j];
a[j]:=a[j+1];
a[j+1]:=m;
end;
end;
end;
write(ans);
end.

0

TheUniverse LV 7 @ 2016-03-31 12:00:56

直接优先队列就行了
#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
priority_queue <int,vector <int>,greater <int> >p;
int n,ans=0;
int main(){
scanf ("%d",&n);
for (int i=1;i<=n;i++){
int x;
scanf ("%d",&x);
p.push(x);
}
while (p.size()>1){
int a=p.top();
p.pop();
int b=p.top();
p.pop();
ans+=a+b;
p.push(a+b);
}
printf ("%d\n",ans);
return 0;
}

0

phosphorus15 LV 7 @ 2016-03-22 13:23:06

手写了个堆排。。稍微有点菜啊。。

#include <iostream>

using std::cin;
using std::cout;
using std::endl;

class Heap{ //手写排序用堆_(:з」∠)_ 
    private:
        int * data;
        int head;
        int len;
        int total;
        int hsize;
    protected:
        int left_child(int x){
            return (x-head+1)*2+head-1;
        }
        int right_child(int x){
            return (x-head+1)*2+head;
        }
        int parent(int x){
            return (x-head+1)/2+head-1;
        }
        void fix_sub(int x){
            if(x>=len)
                return;
            int smallest = x;
            if(left_child(x)<len&&data[left_child(x)]<data[smallest]){
                smallest = left_child(x);
            }
            if(right_child(x)<len&&data[right_child(x)]<data[smallest]){
                smallest = right_child(x);
            }
            if(smallest!=x){
                int swp = data[x];
                data[x] = data[smallest];
                data[smallest] = swp;
                fix_sub(smallest);
            }
        }
    public:
        Heap(int * p,int length){
            this->data = p;
            this->head = 0;
            this->total = 0;
            this->len = length;
            this->hsize = length;
        }
        void build_heap(){
            for(int x=(len+head)/2;x>=head;x--){
                fix_sub(x);
            }
        }
        int size(){
            return hsize;
        }
        int pop(){
            head++;
            hsize--;
            int tmp = data[len-1];
            data[len-1] = data[head];
            data[head] = tmp;
            build_heap();
            return data[head-1];
        }
        void insert(int x){ //这个方法很不安全。。仅仅对于这道题适用 
            hsize++;
            head--;
            data[head]=x;
            fix_sub(head);
        }
        int next(){
            int a=pop(),b=pop();
            total+=a+b;
            insert(a+b);
            return size();
        }
        void operator --(int x){
            total+=data[len-1]+data[len-2];
        }
        int operator ++(int x){
            return next();
        }
        operator int(){
            return total;
        }
        void to_string(){
            for(int x=head;x!=head+hsize;x++){
                cout<<x<<"-"<<data[x]<<" ";
            }
            cout<<endl;
        }
};

int main(int argc,char ** argv){
    int n,*a;
    cin>>n;
    a = new int[n];
    for(int x=0;x!=n;x++){
        cin>>a[x];
    }
    Heap* heap = new Heap(a,n); //堆排序?2333 
    heap->build_heap(); //建堆 
    /*for(int x=0;x!=n;x++){
        cout<<a[x]<<endl;
    }*/
    while(((*heap)++)>2); //论运算符重载_(:з」∠)_ 
    (*heap)--;
    cout<<(int)(*heap)<<endl;
    return 0;
}

0

张大海 LV 7 @ 2016-03-12 16:05:33

这题弱智

张大海 @ 2016-03-12 16:05:54

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int n,k,i,a,b;
cin>>n;
priority_queue<int, vector<int>, greater<int> >P;
for(i=0;i<n;i++)
{
cin>>k;
P.push(k);
}
int he=0;
for(i=1;i<n;i++)
{
a=P.top();
P.pop();
b=P.top();
P.pop();
he+=a+b;
P.push(a+b);
}
cout<<he<<endl;
system ("pause");
return 0;
}
527671349 @ 2016-03-12 16:06:15

niruozhi

0

527671349 LV 4 @ 2016-03-12 16:02:00

#include <queue>
using namespace std;
int main()
{
int n,i,a,b;
cin>>n;
priority_queue<int, vector<int>, greater<int> > Q;
for(i=0;i<n;i++)
{
cin>>a;

Q.push(a);

}
int ans=0;
for(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;

//system("pause") ;
return 0;
}

0

NERvGear LV 8 @ 2016-03-12 16:01:24

编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 704 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 552 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 556 KiB, score = 10

测试数据 #4: Accepted, time = 15 ms, mem = 592 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 636 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 704 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 704 KiB, score = 10

测试数据 #8: Accepted, time = 15 ms, mem = 704 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 700 KiB, score = 10

Accepted, time = 90 ms, mem = 704 KiB, score = 100

题解

535 条题解

优先队列

合并果子

信息

状态

开发

支持

题解

535 条题解

优先队列

合并果子

信息

状态

开发

支持

还没有账户？

登录