看看吧。悬关注!
题目描述
SH书店有n个矩形,第i个矩形的高度为 hi,宽度为wi。小实可以对任意一个矩形进行若干次旋转,每次旋转可以让矩形顺时针旋转 90度,即每次旋转矩形的高度和宽度会进行交换。现在小实想要知道能否找到一种旋转方案,使得n个矩形位置不变,矩形的高度依次不递增。
输入
输入一行一个正整数T,表示数据的组数
对于每组数据
第一行输入一个正整数n,表示矩形的个数 接下来n行,每行两个正整数 hi,wi,表示一个矩形的高度和宽度.
输出
输出共T行,每行一个字符串,第i行的字符串表示第i组数据的答案.对于第i组数据,如果能够找到一种旋转方案满足条件,则输出 Yes,否则输出 No
样例输入
2
3
30 20
25 15
28 20
3
30 20
10 20
25 25
样例输出
Yes
No
提示
第一组数据只需要翻转第三个矩形,则可以达到要求,高度分别为30,25,20.
对于第二组数据,无论怎么旋转第 3 个矩形的高度一定会大于第 2的矩形的高度。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t, n, x, y, now;
void work() {
now = LLONG_MAX;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> x >> y;
if(now >= max(x, y)) now = max(x, y);
else if(now >= min(x, y)) now = min(x, y);
else {
cout << "No\n";
return;
}
}
cout << "Yes\n";
return;
}
signed main() {
cin >> t;
while(t--) work();
return 0;
}
咋调
用贪心法,每个矩形旋转后,在高度不超过前面的矩形的条件下,高度最大,给后面的矩形留最大的范围。
ksgpjhqf 能给代码吗
不要回答他,这是一道C++比赛的题
不知道你这个问题是否已经解决, 如果还没有解决的话: