题目描述：
一堆东西，每次拿出两个不同的东西合。要最终合出来的最多。并且要贪心的买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的情况。
代码：
1#include <iostream> 2#include <cstdio> 3#include <cstring> 4#include <string> 5#include <cmath> 6#include <ctype.h> 7#include <limits.h> 8#include <cstdlib> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <map> 13#include <stack> 14#include <set> 15#include <bitset> 16#include <assert.h> 17#define CLR(a) memset(a, 0, sizeof(a)) 18#define REP(i, a, b) for(ll i = a;i < b;i++) 19typedef long long ll; 20 21using namespace std; 22 23const ll maxn = 1e5 + 100; 24struct info 25{ 26 ll a, b, num; 27 info(ll _a = 0, ll _b = 0, ll _num = 0) 28 { 29 a = _a; 30 b = _b; 31 num = _num; 32 } 33 bool operator < (const info & other) const 34 { 35 if(a == other.a) 36 { 37 return b < other.b; 38 } 39 return a < other.a; 40 } 41}; 42 43ll maxA[maxn], sum, maxa, maxi; 44ll a[maxn]; 45ll n; 46ll tot; 47vector<info> ans; 48vector<info> ansPro; 49void killIt(ll key) 50{ 51 for(ll i =1; i<=n; i++) 52 { 53 if(i != key && a[i] > 0 && a[key]>0) 54 { 55 ll sub = min(a[i], a[key]); 56 if(sub > 0) 57 { 58 59 60 61 ans.push_back(info(min(i, key), max(i, key), sub)); 62 a[i]-=sub; 63 a[key] -= sub; 64 } 65 } 66 } 67} 68 69void outPut() 70{ 71 sort(ans.begin(), ans.end()); 72// ll resSum = 0; 73// ansPro.clear(); 74// for(ll i = 0; i<ans.size(); i++) 75// { 76// if(ans[i].num != 0) 77// { 78// ansPro.push_back(ans[i]); 79// } 80// } 81// ans.clear(); 82// sort(ansPro.begin(), ansPro.end()); 83// for(ll i = 0; i<ansPro.size(); i++) 84// { 85// resSum += ansPro[i].num; 86// if(i!=0) 87// { 88// if(ansPro[i].a == ans[ans.size()-1].a && ansPro[i].b == ans[ans.size()-1].b) 89// { 90// ans[ans.size()-1].num += ansPro[i].num; 91// } 92// else 93// { 94// ans.push_back(ansPro[i]); 95// } 96// } 97// else 98// { 99// ans.push_back(ansPro[i]); 100// } 101// } 102 //ll tsum = 0; 103 ll tempAns = ans.size(); 104 printf("%I64d\n", tempAns); 105 for(ll i = 0; i<ans.size(); i++) 106 { 107 //tsum += ans[i].num; 108 printf("%I64d %I64d %I64d\n", ans[i].a, ans[i].b, ans[i].num); 109 } 110 //printf("%d -----\n", tsum); 111} 112ll gettot(ll mm, ll sum) 113{ 114 if(mm <= sum-mm) 115 return sum/2; 116 return sum-mm; 117} 118ll solve(ll &now1, ll &now2) 119{ 120 ll sub = min(a[now1], a[now2]); 121 ll tmpMax = max(a[now1],a[now2])-sub; 122 ll tmpSum = sum - sub*2; 123 tmpMax = max(maxA[now2+1], tmpMax); 124 ll tmptot = gettot(tmpMax, tmpSum); 125 126 if(tmptot+sub==tot) 127 { 128 129 130 131 sum = tmpSum; 132 a[now1]-=sub; 133 a[now2]-=sub; 134 tot -= sub; 135 ans.push_back(info(now1, now2, sub)); 136 if(a[now2]==0&&a[now1]==0) 137 { 138 now1=now2+1; 139 now2=now1+1; 140 } 141 else if(a[now2]==0) 142 { 143 now2++; 144 } 145 else 146 { 147 now1 = now2; 148 now2++; 149 } 150 return 1; 151 } 152 else 153 { 154 ll l = 0, r = sub; 155 while(l < r) 156 { 157 ll mid = (l+r)/2; 158 tmpSum = sum-2*mid; 159 tmpMax = max(a[now1],a[now2])-mid; 160 tmpMax = max(tmpMax, maxA[now2+1]); 161 tmptot = gettot(tmpMax, tmpSum); 162 if(tmptot+mid==tot) 163 { 164 l = mid+1; 165 } 166 else 167 { 168 r = mid; 169 } 170 } 171 r--; 172 if(r!=0) 173 ans.push_back(info(now1, now2, r)); 174 ll maxI = now1, maxA = a[now1]-r; 175 sum -= 2*r; 176 a[now1] -= r; 177 a[now2] -= r; 178 for(ll i = now2;i<=n;i++) 179 { 180 if(a[i]>maxA) 181 { 182 maxA = a[i]; 183 maxI = i; 184 } 185 } 186 killIt(maxI); 187 return 0; 188 } 189} 190void gao() 191{ 192 sum = 0; 193 for(ll i = 1; i<=n; i++) 194 { 195 sum += a[i]; 196 } 197 maxi = max_element(a+1, a+1+n)-a; 198 maxa = a[maxi]; 199 a[n+1] = 0; 200 maxA[n+1]=0; 201 for(ll i = n;i>=1;i--) 202 { 203 maxA[i]=max(maxA[i+1], a[i]); 204 } 205 ans.clear(); 206 if(!(maxa>=sum-maxa)) 207 { 208 tot = sum/2; 209 ll l = 1, r = 2; 210 while(r<=n) 211 { 212 ll flag = solve(l, r); 213 if(flag==0) 214 break; 215 } 216 } 217 else 218 { 219 killIt(maxi); 220 } 221 outPut(); 222} 223 224int main() 225{ 226 //freopen("11Kin.txt", "r", stdin); 227 //freopen("1out.txt", "w", stdout); 228 freopen("magic.in", "r", stdin); 229 freopen("magic.out", "w", stdout); 230 while(scanf("%I64d", &n)!=EOF) 231 { 232 for(ll i =1; i<=n; i++) 233 { 234 scanf("%I64d", &a[i]); 235 } 236 gao(); 237 } 238 return 0; 239}
本文分享 CSDN - ruclion。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。