• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

CodeforcesRound#263(Div.2)C(贪心,联想到huffman算法)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

数学家伯利亚在《怎样解题》里说过的解题步骤第二步就是迅速想到与该题有关的原型题。(积累的重要性!)

对于这道题,可以发现其实和huffman算法的思想很相似(可能出题人就是照着改编的)。当然最后只是输出cost,就没必要建树什么的了。只要理解了huffman算法构造最优二叉树的思路,就按那么想就知道每个a[i]要加多少次了。

当然这道题没想到这些也可以找出规律的,就是一种贪心思想。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
#define INF 1000000000
#define eps 1e-8
#define pii pair<int,int>
#define LL long long int
const int maxn=310009;
int n;
LL ans=0,a[maxn];
int main()
{
    //freopen("in6.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%I64d",&a[i]);
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n-1;i++) ans+=(i+1)*a[i];
    ans+=n*a[n];
    cout<<ans<<endl;
}

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap