[Codeforces 496E] Distributing Parts
2024-09-04 12:36:25
[题目链接]
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 ; }
最新文章
- Android开发之广播
- Java框架的思考
- Swift学习的新工具---REPL
- 色情不是我的所有——在法律边缘起舞的 FC2
- SQL 去除小数点后无效 0 的方法
- 私有静态方法private static method-值得用吗?
- UML中类图的符号解释
- ORACLE PL/SQL编程:把触发器说透
- 使用google的pprof工具以及在gin中集成pprof
- 洛谷 P4705 玩游戏 解题报告
- Jmeter(八)HTTPCookie管理器
- Oracle EBS INV创建保留
- Java读取json文件并对json数据进行读取、添加、删除与修改操作
- [USACO08NOV]Time Management
- 2018.07.01 洛谷小B的询问(莫队)
- Yii 中Criteria常用方法
- Curl Methods
- 新年开篇-ERP和OA集成步骤
- codeblocks快捷键(转)
- PHP扩展--taint检测隐藏漏洞