444 D. Ratings and Reality Shows

一个模特有两种活动。

① 拍照片,挣钱 a。 ②开演唱会,花费b

给定模特这两种工作的时间表。

模特可以选定一个时间举办一个座谈会,那么他拍照片的钱变c。开演唱会会花费d。

要求在模特座谈会之前和后len天(当天凌晨即可生效) 都不能赔钱。 要求你输出最小的座谈会天数。 没有输出-1.。

ll n, a, b, c, d, st, len;
struct node
{
ll tim, tp;
} p[N];
ll calc1(ll x)
{
if(x==-1)
return 0;
return x ? a : -b;
}
ll calc2(ll x)
{
return x ? c : -d;
}
ll tail = 0;
ll mi = inf;
ll res = 0;
ll sum = 0;
int main()
{
sdf(n), sdf(a), sdf(b), sdf(c), sdf(d), sdf(st), sdf(len);
p[0].tim = -1, p[0].tp = -1;
p[n + 1].tim = 1e18;//这里开大点,0x3f3f3f3f不够
For(i, 1, n)
sdf(p[i].tim),
sdf(p[i].tp);
For(i, 0, n)
{
sum += calc1(p[i].tp);
if (sum < -st)
{
cout << -1;
return 0;
}
while (p[tail + 1].tim <= p[i].tim + len)
{
++tail, res += calc2(p[tail].tp);
chkmin(mi, res);
}
if (sum + mi >= -st)
{
cout << p[i].tim + 1;
return 0;
}
mi -= calc2(p[i + 1].tp);
res -= calc2(p[i + 1].tp);
}
return 0;
}
上一篇:C++ 容器:顺序性容器、关联式容器和容器适配器


下一篇:8、泛型程序设计与c++标准模板库2.5容器适配器