题目点此
题意:K个小伙伴买N个多花,老板很奇葩,不想买太多花,如果有人已经买过x朵花了,那么买下一朵花就要付x+1倍的价格。给出每朵花的价格,求最少花多少钱都把花买下。
分析:每个小伙伴买花时肯定是先买原价贵的,不然就吃亏了是不是。所以贪心策略就是把价格排序下,先让每个小伙伴把一血献给最贵的那几朵花,每次都买剩下的花最贵的那几朵,这样就是最优的了。
一遍遍历即可,复杂度为O(n)。
代码:
/*
* Author: illuz <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: Flowers.cpp
* Lauguage: C/C++
* Create Date: 2013-09-06 15:46:01
* Descripton: flowers
*/
#include <cstdio>
#include <algorithm>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 110;
int a[MAXN];
int n, k;
LL sum = 0;
bool cmp(int a, int b) {
return a > b;
}
int main() {
scanf("%d%d", &n, &k);
rep(i, n) scanf("%d", &a[i]);
sort(a, a + n, cmp);
rep(i, n) sum += a[i] * (i / k + 1);
printf("%lld\n", sum);
return 0;
}
分享到:
相关推荐
Algorithm-Problem-Solving-with-Algorithms-and-Data-Structures-using-Python.zip,使用python的算法和数据结构解决问题的代码,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
problem-solving-with-algorithms-and-data-structure-using-python 中文版
python-algorithms-mastering-basic-algorithms-in-the-python-language.9781430232377.53502.pdf
H/\cker r/\nk算法
python-algorithms-mastering-basic-algorithms-in-the-python-language(英文正版)1
Neo4j,用户手册,涵盖所有集成的图算法及应用场景,非常适合图算法的学习和应用
data-algorithms-book, 数据算法书的MapReduce Spark Java和 Scala 数据算法。作者:Mahmoud Parsian ( mahmoud.parsian@yahoo.com )标题:数据算法:使用Hadoop和 Spark 扩展的食谱。这个GitHub存储库将托管所有的...
Machine_Learning_Algorithms-master,Machine_Learning_Algorithms-master 配套数据集及源代码 Machine_Learning_Algorithms-master,Machine_Learning_Algorithms-master 配套数据集及源代码
GitHub上的hackerrank解决方案| Java中的hackerrank教程|英特尔:registered:开发人员专区hackerrank 30天的代码解决方案| hackerrank算法解决方案| hackerrank破解编码面试解决方案| hackerrank通用编程解决方案| ...
A-Comparative-Study-of-Reco-mmendation-Algorithms-in-E-Commerce-Applications
This e-book is devoted to global optimization algorithms, which are methods to find optimal solutions for given problems.
This paper presents the top 10 data mining algorithms identified by the IEEE International Conference on Data Mining (ICDM) in December 2006: C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, ...
Beginning Algorithms----学习算法的好书,介绍各种算法!!!
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。...
遗传算法Python程序 Hands-On-Genetic-Algorithms-with-Python-master.zip
Study-guide-for-Algorithms-in-Bioinformatics-A-Practical-Introduction
Image-Fusion-Algorithms-and-Applications.pdf
Algorithms - Robert Sedgewick, Kevin Wayne Algorithms - Robert Sedgewick, Kevin Wayne 视频 算法 普林斯顿
Genetic-Algorithms-with-Python.pdf
computer-arithmetic-algorithms-2nd-edition-Behrooz-Parhami.pdf