uoj problem 10
题目大意:
题解:
其实vfk的题解很详细.
那我就写一写我的理解吧.
首先拿到这道题我们就会去想枚举优先级然后判定.
分析一下我们发现优先级是具有单调性的,所以我们可以二分.
这样直接就能拿到90%的分数.
然后题解上说:
WTF...我好是第一次用扫描优化有单调性的题...
我们扫描一边所有的题目,先将未知的优先级按照\(-inf\)算,计算出所有的任务的结束时间
设未知优先级的任务编号为x,结束时间为T
那么我们计算出所有在\([t_x,T]\)内的工作量,然后我们将所有的任务按照优先级排序.
现在我们就确定一个优先级是的所有优先级\(<\)它的任务的工作量之和等于\(s_x\)
不难发现这样是对的.
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch=='-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 300010;
struct Node{
ll t;
ll s,p,id,idx;
bool friend operator < (const Node &a,const Node &b){
return a.p < b.p;
}
}a[maxn],b[maxn];
inline bool cmp(const Node &a,const Node &b){
return a.t < b.t;
}
ll n,T,Xl,Xr,ans[maxn];
inline void add(ll l,ll r,int id){
ll x = min(r,Xr) - max(l,Xl) + 1;
if(x <= 0) return ;
b[id].s += x;
}
inline void work(int n){
priority_queue<Node>q;
ll la = 0;
for(int i=1;i<=n;++i){
ll ti = a[i].t - 1;
if(ti > la){
ll x = ti - la,y = 0;
while(!q.empty() && q.top().s <= x){
Node no = q.top();q.pop();
x -= no.s;y += no.s;
ans[no.id] = la + y;
add(la+y-no.s+1,la+y,no.idx);
}
if(!q.empty() && x){
Node no = q.top();q.pop();
add(la+y+1,la+y+x,no.idx);
no.s -= x;q.push(no);
}
}
while(a[i].t == a[i+1].t){
q.push(a[i]);
++ i;
}q.push(a[i]);la = a[i].t - 1;
}
}
int main(){
read(n);int tx;
for(int i=1;i<=n;++i){
read(a[i].t);
read(a[i].s);
read(a[i].p);
a[i].id = i;
}
a[n+1].t = 1LL<<60;
a[n+1].s = 1e9;
a[n+1].p = -1e9;
a[n+1].id = n+1;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i){
a[i].idx = i;
b[i] = a[i];b[i].s = 0;
if(a[i].p == -1){
b[i].p = a[i].p = 0;
tx = i;
}
}
read(T);--T;
Xl = a[tx].t;Xr = T;work(n+1);
sort(b+1,b+n+1);
ll s = a[tx].s,ans1 = 0;
for(int i=1;i<=n;++i){
s -= b[i].s;
if(s == 0 && b[i].p + 1 != b[i+1].p){
ans1 = b[i].p + 1;
break;
}
}
printf("%lld\n",ans1);
a[tx].p = ans1;
work(n+1);
for(int i=1;i<=n;++i){
printf("%lld",ans[i]+1);
if(i != n) putchar(' ');
else putchar('\n');
}
return 0;
}