会python真的可以为所欲为0(回)
355天前
这里还有人吗1(回)
541天前这里还有人吗0(回)
541天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
765天前到处都是羊，不想上班0(回)
845天前
鸽子
0(回)
849天前
问题描述：
在一个操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次至少选2 堆最多选k堆石子合并成新的一堆，合并的费用为新的一堆的石子数。试设计一个算法，计算出将n堆石子合并成一堆的最大总费用和最小总费用。
编程任务：
对于给定n堆石子,编程计算合并成一堆的最大总费用和最小总费用。
Input
测试数据的第1 行有2个正整数n和k，表示有n堆石子，每次至少选2堆最多选k堆石子合并。第2行有n个数，分别表示每堆石子的个数。
Output
输出最大总费用和最小总费用，用一空格隔开，每个答案一行。
Sample Input
7 3
45 13 12 16 9 5 22
Sample Output
593 199
#include<iostream> |
#include<algorithm> |
#include<vector> |
using namespace std; |
bool cmp ( int a, int b ) |
{ |
return a>b; |
} |
void Insert ( vector<int> &f, int pos, int value ) |
{ |
for ( int i = f.size() - 1; i > pos; i-- ) |
{ |
f[i] = f[i - 1]; |
} |
f[pos] = value; |
} |
int Find ( vector<int> f, int value ) |
{ |
int pos = f.size() - 1; |
while ( pos >= 0 && f[pos] < value ) |
{ |
pos--; |
} |
return pos + 1; |
} |
int MaxNum ( vector<int> f ) |
{ |
sort ( f.begin(), f.end() ); |
int Max; |
Max = 0; |
while ( f.size() >= 2 ) |
{ |
int sum = f[f.size() - 1] + f[f.size() - 2]; |
Max = Max + sum; |
f.resize ( f.size() - 1 ); |
f[f.size() - 1] = sum; |
} |
return Max; |
} |
int MinNum ( vector<int> f, int len ) |
{ |
sort ( f.begin(), f.end(), cmp ); |
int Min; |
Min = 0; |
while ( f.size() >= len ) |
{ |
int sum = 0; |
for ( int i = f.size() - 1; i >= f.size() - len && i >= 0; i-- ) |
{ |
sum = sum + f[i]; |
} |
Min = Min + sum; |
f.resize ( f.size() - len + 1 ); |
if ( f.size() > len ) |
{ |
int pos = Find ( f, sum ); |
Insert ( f, pos, sum ); |
} |
else if ( f.size() != 1 ) |
{ |
f[f.size() - 1] = sum; |
for ( int i = 0; i < f.size(); i++ ) |
{ |
Min = Min + f[i]; |
} |
break; |
} |
else |
{ |
break; |
} |
} |
return Min; |
} |
bool run() |
{ |
int n, m; |
if ( ! ( cin >> n >> m ) ) return false; |
vector<int> f ( n ); |
for ( int i = 0; i < n; i++ ) |
{ |
cin >> f[i]; |
} |
int Max, Min; |
Max = MaxNum ( f ); |
while ( f.size() % ( m - 1 ) != 1 ) |
{ |
f.push_back ( 0 ); |
} |
Min = MinNum ( f, m ); |
cout << Max << " " << Min << endl; |
return true; |
} |
int main() |
{ |
while ( run() ); |
return 0; |
} |
初级程序员
by: Lyw 发表于：2019-09-24 11:37:21 顶(0) | 踩(0) 回复
好
回复评论