AT945 高橋君とお肉 题解
题意简述:
有 n 个数 a1~ an,将它们分成两组,这两组的和的最大的那一个的最小值。
解题思路:
为了使烤肉总时间尽可能断,我们要尽量把时间平均分配给这两台机器,以减少机器空闲的时间浪费。
所以,解决思路大致为:将烤肉的时间由大到小排序(可能不排也可以,自己没试过),依次进入两个累加器 sum1 和 sum2 中,如果其中一个较大,那么就将其加入另一个 sum 中。最后输出 sum1 和 sum2 的最大值。
code:
#include<bits/stdc++.h> using namespace std; int n,m,sum1,sum2; int t[5]; int main(){ cin >> n; for(int i = 1;i <= n;i ++) cin >> t[i]; sort(t+1,t+1+n); sum1 = t[n]; for(int i = n-1;i >= 1;i --){ if(sum1 > sum2)sum2 += t[i]; else sum1 += t[i]; } cout<<max(sum1,sum2)<<endl; return 0; }