http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4190題意即通過合并求最大的合并數與最小的合并數之差。
最大合并數策略：每次選取最小的兩個數合并；
最小合并數策略：每次選最大的K個數合并。
注意：大數運算。
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<iterator>
#include<string.h>
using namespace std;
const int MAXN = 102;
class bigInt
{
public:
int num[302], len;
bigInt() { num[0] = 0, len = 0; }
bigInt operator=(const int &a)
{
int tmp = a;
len = 0;
while (tmp)
num[len++] = tmp % 10, tmp /= 10;
if (!len) num[0] = 0, len = 1;
}
bigInt(const int &a)
{
int tmp = a;
len = 0;
while (tmp)
num[len++] = tmp % 10, tmp /= 10;
if (!len) num[0] = 0, len = 1;
}
bool operator<(const bigInt &a)
{
if (a.len != len)
return len < a.len;
for (int i = len - 1; i >= 0; i--)
if (num[i] != a.num[i])
return num[i] < a.num[i];
return false;
}
bigInt operator+(const bigInt &a)
{
bigInt res;
int i, j, c = 0, adda, addb;
for (i = 0, j = 0; i < len || j < a.len || c; )
{
adda = 0, addb = 0;
if (i < len)
adda = num[i++];
if (j < a.len)
addb = a.num[j++];
res.num[res.len++] = (adda + addb + c) % 10;
c = (adda + addb + c) / 10;
}
return res;
}
bigInt operator-(const bigInt &b)
{
bigInt res;
int i, j, c = 0, suba, subb;
for (i = 0, j = 0; i < len || j < b.len || c; )
{
suba = 0, subb = 0;
if (i < len)
suba = num[i++];
if (j < b.len)
subb = b.num[j++];
res.num[res.len++] = (suba - subb + c + 10) % 10;
c = (suba - subb + c + 10) / 10 - 1;
}
for (i = res.len - 1; i > 0; i--)
if (res.num[i]) break;
res.len = i + 1;
return res;
}
bigInt operator*(const bigInt &b)
{
bigInt res;
int i, j, c, now, mulb, tmp;
memset(res.num, 0, sizeof(int) * (len + b.len));
for (i = 0; i < len; i++)
{
now = i, c = 0;
for (j = 0; j < b.len || c; )
{
mulb = 0;
if (j < b.len)
mulb = b.num[j++];
tmp = res.num[now] + num[i] * mulb + c;
res.num[now++] = tmp % 10;
c = tmp / 10;
}
}
for (i = len + b.len - 1; i > 0; i--)
if (res.num[i]) break;
res.len = i + 1;
return res;
}
bigInt operator/(const bigInt &b)
{
bigInt res, diva;
int i, j, c;
for (i = len - 1; i >= 0; i--)
{
if (diva.len > 1 || diva.num[0])
{
for (j = diva.len - 1; j >= 0; j--)
diva.num[j + 1] = diva.num[j];
diva.len++;
}
diva.num[0] = num[i];
if (!diva.len) diva.len = 1;
res.num[i] = 0;
while (!(diva < b))
diva = diva - b, res.num[i]++;
}
for (i = len - 1; i > 0; i--)
if (res.num[i]) break;
res.len = i + 1;
return res;
}
bigInt operator%(const bigInt &b)
{
bigInt res, diva;
int i, j, c;
for (i = len - 1; i >= 0; i--)
{
if (diva.len > 1 || diva.num[0])
{
for (j = diva.len - 1; j >= 0; j--)
diva.num[j + 1] = diva.num[j];
diva.len++;
}
diva.num[0] = num[i];
if (!diva.len) diva.len = 1;
res.num[i] = 0;
while (!(diva < b))
diva = diva - b, res.num[i]++;
}
for (i = diva.len - 1; i > 0; i--)
if (diva.num[i]) break;
diva.len = i + 1;
return diva;
}
void display()
{
int i;
for (i = len - 1; i > 1; i--)
if (num[i]) break;
for (; i >= 0; i--)
printf("%d", num[i]);
printf("\n");
}
};
bool cmp(bigInt a, bigInt b)
{
return (b<a);
}
bool cmp1(bigInt a, bigInt b)
{
return (a<b);
}
int main()
{
int x, n, k;
vector<bigInt>v;
vector<bigInt>t;
vector<bigInt>tmp;
bigInt tmpx;
while(scanf("%d%d",&n,&k)!=EOF)
{
v.clear();
t.clear();
for(int i = 0; i < n; i++)
{
scanf("%d",&x);
bigInt tmp_x = x;
v.push_back(tmp_x);
}
copy(v.begin(),v.end(),back_inserter(t));
while(v.size()>1)
{
tmp.clear();
sort(v.begin(),v.end(),cmp);
if(v.size()> k){
for(int i = k; i < v.size(); i++){
tmp.push_back(v[i]);
}
tmpx = 1;
for(int i = 0; i < k; i++){
tmpx = tmpx * v[i];
}
tmpx = tmpx + 1;
tmp.push_back(tmpx);
v.swap(tmp);
}else{
tmpx = 1;
for(int i = 0; i < v.size(); i++)
tmpx = tmpx * v[i];
tmpx = tmpx + 1;
tmp.push_back(tmpx);
v.swap(tmp);
}
}
while(t.size()>1)
{
tmp.clear();
sort(t.begin(),t.end(),cmp1);
if(t.size()>2){
for(int i = 2; i < t.size(); i++){
tmp.push_back(t[i]);
}
tmpx = 1;
for(int i = 0; i < 2; i++){
tmpx = tmpx*t[i];
}
tmpx = tmpx + 1;
tmp.push_back(tmpx);
t.swap(tmp);
}else{
tmpx = 1;
for(int i = 0; i < t.size(); i++)
tmpx = tmpx * t[i];
tmpx = tmpx + 1;
tmp.push_back(tmpx);
t.swap(tmp);
}
}
tmpx = t[0]-v[0];
tmpx.display();
}
return 0;
}