Java教程

Namomo Div1 每日一题 排序

本文主要是介绍Namomo Div1 每日一题 排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

排序

思路:
  首先我们要满足构造出来的序列保持不增的顺序,所以一开始先按\(a_i\)从大到小排序;其次要考虑攻击力的增益之后,还要满足不增,那么我们就考虑最极端的情况,两个相邻的人\(A,B\),将整个序列所有的增益都给\(A\),将\(A\)的增益给除\(B\)以外的任意一个,只要还能够满足\(A'\geq B\),那么他就是正确的。

void solve() {
    int n;
    std::cin >> n;
    std::vector<std::pair<int,int>> v(n);

    auto cmp = [&] (std::pair<int,int> A, std::pair<int,int> B) -> bool {
        if (A.first == B.first) return A.second < B.second;
        return A.first > B.first;
    };
    for (int i = 0; i < n; i ++ ) std::cin >> v[i].first >> v[i].second;
    std::sort(v.begin(), v.end(), cmp);
    if (n == 2) {
        std::cout << (v[0].first + v[1].second >= v[1].first + v[0].second || 
            v[1].first + v[0].second >= v[0].first + v[1].second ? "Yes\n" : "No\n");
        return ;
    }
    i64 sum = 0;
    for (int i = 0; i < n; i ++ ) sum += v[i].second;
    for (int i = 1; i < n; i ++ ) 
        if (sum + v[i].first - v[i].second > v[i - 1].first) {
            std::cout << "No\n";
            return ;
        }
    std::cout << "Yes\n";
}

这篇关于Namomo Div1 每日一题 排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!