[题目链接]

https://codeforces.com/contest/496/problem/E

[算法]

按右端点排序 , 每个乐曲优先选取的左端点最大的演奏家

用std :: set维护贪心

时间复杂度 : O(NlogN)

[代码]

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + ;
const int inf = 2e9; int n , m; struct info
{
int l , r , k , home;
bool type;
} a[MAXN << ]; set< pair<int,pair<int,int> > > s;
int ans[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }
template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }
template <typename T> inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
inline bool cmp(info a,info b)
{
if (a.r != b.r) return a.r > b.r;
else return a.type > b.type;
} int main()
{ read(n);
for (int i = ; i <= n; i++)
{
int l , r;
scanf("%d%d",&l,&r);
a[i] = (info){l,r,,i,false};
}
read(m);
for (int i = ; i <= m; i++)
{
int l , r , k;
scanf("%d%d%d",&l,&r,&k);
a[n + i] = (info){l,r,k,i,true};
}
sort(a + ,a + (n + m) + ,cmp);
for (int i = ; i <= n + m; i++)
{
if (a[i].type)
{
s.insert(make_pair(a[i].l,make_pair(a[i].k,a[i].home)));
continue;
} else
{
s.insert(make_pair(a[i].l,make_pair(inf,inf)));
set< pair<int,pair<int,int> > > :: iterator it = s.find(make_pair(a[i].l,make_pair(inf,inf)));
if (it == s.begin())
{
printf("NO\n");
return ;
}
it--;
pair< int,pair<int,int> > tmp = (*it);
s.erase(it);
ans[a[i].home] = tmp.second.second;
if (tmp.second.first > ) s.insert(make_pair(tmp.first,make_pair(tmp.second.first - ,tmp.second.second)));
it = s.find(make_pair(a[i].l,make_pair(inf,inf)));
s.erase(it);
}
}
printf("YES\n");
for (int i = ; i <= n; i++) printf("%d ",ans[i]);
printf("\n"); return ; }

最新文章

  1. Android开发之广播
  2. Java框架的思考
  3. Swift学习的新工具---REPL
  4. 色情不是我的所有——在法律边缘起舞的 FC2
  5. SQL 去除小数点后无效 0 的方法
  6. 私有静态方法private static method-值得用吗?
  7. UML中类图的符号解释
  8. ORACLE PL/SQL编程:把触发器说透
  9. 使用google的pprof工具以及在gin中集成pprof
  10. 洛谷 P4705 玩游戏 解题报告
  11. Jmeter(八)HTTPCookie管理器
  12. Oracle EBS INV创建保留
  13. Java读取json文件并对json数据进行读取、添加、删除与修改操作
  14. [USACO08NOV]Time Management
  15. 2018.07.01 洛谷小B的询问(莫队)
  16. Yii 中Criteria常用方法
  17. Curl Methods
  18. 新年开篇-ERP和OA集成步骤
  19. codeblocks快捷键(转)
  20. PHP扩展--taint检测隐藏漏洞

热门文章

  1. Ubuntu终端常用快捷键汇总
  2. day 21 03 补全异常处理
  3. 91-Williams' Percent Range 威廉指标.(2015.7.4)
  4. A - 栈
  5. STM32F407 按键输入实验 库函数版 个人笔记
  6. HDU 1016 素数环问题
  7. vue2.0一个书城实例
  8. Linux下汇编语言学习笔记15 ---
  9. hdu - 1104 Remainder (bfs + 数论)
  10. Meeting 加虚拟边