算法基础之耍杂技的牛

2024-01-08 21:40:38

耍杂技的牛

  • 核心思想: 贪心

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

      • 比较交换位置后的危险系数最大值
      • Wi + Si > Wi+1 + Si+1 则交换前大 交换后更优 需要交换
      • 因此 按照W+S从小到大排序 就是最优解 再计算危险系数
    • 在这里插入图片描述

    •   #include<iostream>
        #include<algorithm>
        
        using namespace std;
        const int N = 100010;
        typedef pair<int,int> PII;  //first存w+s second存w
        
        PII 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;
        }
      

文章来源:https://blog.csdn.net/Pisasama/article/details/135466173
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。