算法基础之耍杂技的牛

本文主要是介绍算法基础之耍杂技的牛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

耍杂技的牛

• 核心思想： 贪心

  • 推公式： 将 i 和 i+1 个奶牛交换位置

    • 比较交换位置后的危险系数最大值
    • 若W_i + S_i > W_i+1 + S_i+1 则交换前大 交换后更优 需要交换
    • 因此 按照W+S从小到大排序 就是最优解 再计算危险系数

  • 

  •   #include<iostream>#include<algorithm>using namespace std;const int N = 100010;typedef pair<int,int> PII;  //first存w+s second存wPII cows[N];int main(){int n;cin>>n;for(int i=0;i<n;i++){int w,s;cin>>w>>s;cows[i] = {w+s,w};}sort(cows,cows+n);  //根据key排序int res = -2e9,sum = 0;for(int i=0;i<n;i++){int w = cows[i].second,s = cows[i].first - w;res = max(res, sum - s);  //求危险系数最大值sum += w;  //用于求危险系数}cout<<res;}
    

这篇关于算法基础之耍杂技的牛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---