题目描述：
一堆东西，每次拿出两个不同的东西合。要最终合出来的最多。并且要贪心的买12 13 14.。。1n 23.。。
http://codeforces.com/gym/100430/attachments/download/2418/20092010-summer-petrozavodsk-camp-andrew-stankevich-contest-36-asc-36-en.pdf
题解：
首先要保证总个数是最多的。怎么算总个数？求一下maxelement，然后sum-maxelement和max值比较，大中小对应情况。
其次要贪心的去取，那么我们最直接的：取12 取13.。。。可以取就一直取，如果取完算一下剩下的东西不能凑成原来的最优的结果的话，那么二分找到最大能够取得那个值。把它给取了。之后一旦发生这样的情况，说明已经到了后面的东西全部都和后面的最高值合并的特殊情况（这一点很重要），我们直接killit就好了。
另外也有一种其他方法：先贪心的合并，然后可能剩余一个有很多数量，再倒着拆已经合好的石头和这个剩余的合并。
重点：
（1）会算最大个数。
（2）按照题目中贪心。不能取的时候发现已经到了特殊情况。
（3）注意max=6 sum-max=7的情况。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <ctype.h>
#include <limits.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#include <assert.h>
#define CLR(a) memset(a, 0, sizeof(a))
#define REP(i, a, b) for(ll i = a;i < b;i++)
typedef long long ll;
using namespace std;
const ll maxn = 1e5 + 100;
struct info
{
ll a, b, num;
info(ll _a = 0, ll _b = 0, ll _num = 0)
{
a = _a;
b = _b;
num = _num;
}
bool operator < (const info & other) const
{
if(a == other.a)
{
return b < other.b;
}
return a < other.a;
}
};
ll maxA[maxn], sum, maxa, maxi;
ll a[maxn];
ll n;
ll tot;
vector<info> ans;
vector<info> ansPro;
void killIt(ll key)
{
for(ll i =1; i<=n; i++)
{
if(i != key && a[i] > 0 && a[key]>0)
{
ll sub = min(a[i], a[key]);
if(sub > 0)
{
ans.push_back(info(min(i, key), max(i, key), sub));
a[i]-=sub;
a[key] -= sub;
}
}
}
}
void outPut()
{
sort(ans.begin(), ans.end());
// ll resSum = 0;
// ansPro.clear();
// for(ll i = 0; i<ans.size(); i++)
// {
// if(ans[i].num != 0)
// {
// ansPro.push_back(ans[i]);
// }
// }
// ans.clear();
// sort(ansPro.begin(), ansPro.end());
// for(ll i = 0; i<ansPro.size(); i++)
// {
// resSum += ansPro[i].num;
// if(i!=0)
// {
// if(ansPro[i].a == ans[ans.size()-1].a && ansPro[i].b == ans[ans.size()-1].b)
// {
// ans[ans.size()-1].num += ansPro[i].num;
// }
// else
// {
// ans.push_back(ansPro[i]);
// }
// }
// else
// {
// ans.push_back(ansPro[i]);
// }
// }
//ll tsum = 0;
ll tempAns = ans.size();
printf("%I64d\n", tempAns);
for(ll i = 0; i<ans.size(); i++)
{
//tsum += ans[i].num;
printf("%I64d %I64d %I64d\n", ans[i].a, ans[i].b, ans[i].num);
}
//printf("%d -----\n", tsum);
}
ll gettot(ll mm, ll sum)
{
if(mm <= sum-mm)
return sum/2;
return sum-mm;
}
ll solve(ll &now1, ll &now2)
{
ll sub = min(a[now1], a[now2]);
ll tmpMax = max(a[now1],a[now2])-sub;
ll tmpSum = sum - sub*2;
tmpMax = max(maxA[now2+1], tmpMax);
ll tmptot = gettot(tmpMax, tmpSum);
if(tmptot+sub==tot)
{
sum = tmpSum;
a[now1]-=sub;
a[now2]-=sub;
tot -= sub;
ans.push_back(info(now1, now2, sub));
if(a[now2]==0&&a[now1]==0)
{
now1=now2+1;
now2=now1+1;
}
else if(a[now2]==0)
{
now2++;
}
else
{
now1 = now2;
now2++;
}
return 1;
}
else
{
ll l = 0, r = sub;
while(l < r)
{
ll mid = (l+r)/2;
tmpSum = sum-2*mid;
tmpMax = max(a[now1],a[now2])-mid;
tmpMax = max(tmpMax, maxA[now2+1]);
tmptot = gettot(tmpMax, tmpSum);
if(tmptot+mid==tot)
{
l = mid+1;
}
else
{
r = mid;
}
}
r--;
if(r!=0)
ans.push_back(info(now1, now2, r));
ll maxI = now1, maxA = a[now1]-r;
sum -= 2*r;
a[now1] -= r;
a[now2] -= r;
for(ll i = now2;i<=n;i++)
{
if(a[i]>maxA)
{
maxA = a[i];
maxI = i;
}
}
killIt(maxI);
return 0;
}
}
void gao()
{
sum = 0;
for(ll i = 1; i<=n; i++)
{
sum += a[i];
}
maxi = max_element(a+1, a+1+n)-a;
maxa = a[maxi];
a[n+1] = 0;
maxA[n+1]=0;
for(ll i = n;i>=1;i--)
{
maxA[i]=max(maxA[i+1], a[i]);
}
ans.clear();
if(!(maxa>=sum-maxa))
{
tot = sum/2;
ll l = 1, r = 2;
while(r<=n)
{
ll flag = solve(l, r);
if(flag==0)
break;
}
}
else
{
killIt(maxi);
}
outPut();
}
int main()
{
//freopen("11Kin.txt", "r", stdin);
//freopen("1out.txt", "w", stdout);
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);
while(scanf("%I64d", &n)!=EOF)
{
for(ll i =1; i<=n; i++)
{
scanf("%I64d", &a[i]);
}
gao();
}
return 0;
}
本文分享 CSDN - ruclion。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
