B. Turn the Rectangles

题目链接

Codeforces Round #497 (Div. 2)--B. Turn the Rectangles

题解

简单题。题意大概是给定n个矩形,判定能否通过旋转使他们的高度变成单调非升序列。
贪心法,每次判断某个矩形时均使它的高度在符合要求的范围内尽可能大。

代码

#include <iostream>
#include <math.h>
#include <algorithm>
using namespace std;
int n, now(0x7fffffff), q1, q2;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> q1 >> q2;
        if (q1 > now && q2 > now) {
            cout << "NO"; return 0;
        }
        else if (max(q1, q2) <= now)now = max(q1, q2);
        else now = min(q1, q2);
    }
    cout << "YES";
}

标签: sortings, greedy

添加新评论