codeforces (C++ In Love )"/>
codeforces (C++ In Love )
题目:
翻译:
思路:
1、在一个集合中有多组线段,如果有不相交的两组线段,则输出YES,否则输出NO。
2、每次操纵可以选择增加一组线段或者删除一组线段后,输出YES或者NO。
3、用flag标记该线段是否还在集合中,flag=1表示在,flag=0表示不在。
4、找到最大起始点和最小的结束点,当最大的起始点减去最小的结束点大于0,则说明存在两组不相交的线段,输出YES;小于等于,则说明不存在,输出NO。
代码:
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct node
{long long begin = 0, end = 0;int flag = 1;
}node;
bool cmp1(node a, node b)
{return a.begin > b.begin;
}
bool cmp2(node a, node b)
{return a.end < b.end;
}
int main()
{int n,k=0;char a;node b[12];long long minend = 1e9, maxbegin = 0;cin >> n;for (int i = 0; i < n; i++){cin >> a;long long c, d;cin >> c >> d;if (a == '+')b[k].begin = c, b[k++].end = d;if (a == '-'){for (int j = 0; j < i; j++){if (b[j].begin == c && b[j].end == d && b[j].flag==1){b[j].flag = 0;break;}}}long long minend = 1e9, maxbegin = 0;int v=0;sort(b, b + k, cmp1);//求maxbegin从大到小排序for (int j = 0; j < k; j++){if (b[j].begin >= maxbegin && b[j].flag == 1){maxbegin = b[j].begin;break;}}sort(b, b + k, cmp2);//求minend从小到大排序for (int j = 0; j < k; j++){if (b[j].end <= minend && b[j].flag == 1){minend = b[j].end;break;}}if (i == 0){cout << "NO" << endl;continue;}if (maxbegin - minend > 0)cout << "YES" << endl;elsecout << "NO" << endl;}
}
结果:
更多推荐
codeforces (C++ In Love )
发布评论