//从这一题我们可以感受到要学会将抽象的题目转化成具体的数学模型,
//比如这一题就将题意中飞机降落时间段的安排转换成了对于多个区间的安排使得各个区间不会相交
//贪心骗分法(每次都让最先没油的飞机先降落,在蓝桥杯官网上只骗了2个数据)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 11, Ultim = 2e5 + 10;
int t[N], d[N], l[N];
struct Deadline
{
int time;
int num;
bool operator< (const Deadline &W)const
{
return time < W.time;
}
}ultim[N];//用来记录各个飞机没有的时间以及对应的飞机编号
int main()
{
int T;
scanf("%d", &T);
while(T --)
{
int now = 0;//实时记录时间
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
scanf("%d%d%d", &t[i], &d[i], &l[i]);
ultim[i].time = t[i] + d[i];//ultim[i].time用来记录各个飞机最晚必须降落的时间
ultim[i].num = i;
}
sort(ultim + 1, ultim + n + 1);
auto x = ultim[1];
int num0 = x.num, time0 = x.time;//num0是最先没油的飞机编号,time0是该飞机最晚必须降落的时间
now = t[num0] + l[num0];
int i;
for(i = 2; i <= n; i ++)//从小到大遍历最快没油的飞机
{
x = ultim[i];
num0 = x.num, time0 = x.time;
if(now > time0)
{
puts("NO");
break;
}
else
{
if(now < t[num0])
now = t[num0] + l[num0];
else now += l[num0];
}
}
if(i == n + 1) puts("YES");
}
return 0;
}
----------------------------------------------------------------------------------------------
//dfs暴搜+贪心
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10;
bool st[N];//记录每一架飞机是否被遍历过
int n;
struct Plane
{
int t, d, l;
}plane[N];
//总结的关于暴搜dfs的做题技巧:
//暴搜dfs除了可以对图进行直接遍历外,我们通常可以选择一个“索引”,对索引进行深搜。
//比如dfs两道模板题:1.对n个数进行全排列是以“排列的位置”为索引,
// 然后在每一轮的递归中,循环所有的数看看谁可以放进这个位置;
// 2.n皇后问题是以棋盘的“每一行”为索引,
// 然后在每一轮的递归中,循环每一列看看哪一列可以放置皇后;
//以飞机降落的顺序为“索引”进行暴力深搜,依次遍历第一个降落的飞机是谁,
//第二个降落的飞机是谁,......,第n架降落的飞机是谁,
//如果n个降落顺序都成功确定下来了,说明飞机可以全部安全降落
bool dfs(int x, int last)//last是指编号为x的飞机降落后的时间点
{
if(x == n) return true;
for(int i = 0; i < n; i ++)
{
int t = plane[i].t, d = plane[i].d, l = plane[i].l;
if(st[i] == 0 && t + d >= last)
{
st[i] = 1;
//这里的判断语句用到了贪心的思想,将飞机从开始降落到完成降落的时间段看作是一个区间,
//而这个区间是可以在一定范围内左右移动的(因为飞机可以在空中盘旋一段时间)
//因此与其选择这个区间靠右边一点的状态,但这样做会增加后边的区间没办法入选的可能性
//(即总会出现与前面已入选的区间出现交集),我们不如之间选择这个区间最靠左边的状态
//(在不与前一个区间出现交集的条件下)
if(dfs(x + 1, max(t, last) + l) == 1) return true;
st[i] = 0;
}
}
return false;
}
int main()
{
int t;
cin >> t;
while(t --)
{
memset(st, 0, sizeof st);
scanf("%d", &n);
for(int i = 0; i < n; i ++)
{
int t, d, l;
scanf("%d%d%d", &t, &d, &l);
plane[i] = {t, d, l};
}
if(dfs(0, 0) == true) puts("YES");
else puts("NO");
}
return 0;
}