专栏文章
P10980 任务安排 4.1【暂无数据】 题解
P10980题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mipjydk3
- 此快照首次捕获于
- 2025/12/03 13:14 3 个月前
- 此快照最后确认于
- 2025/12/03 13:14 3 个月前
前置知识
解法
因为暂时没有数据,所以不保证代码一定正确。
代码
CPP#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
ll f[300010],t[300010],c[300010],k[300010],p[300010],tmp[300010],n,s;
deque<ll>q;
bool cmpk(ll a,ll b)
{
return k[a]<k[b];
}
ll x(ll i)
{
return c[i];
}
ll y(ll i)
{
return f[i];
}
bool cmpx(ll a,ll b)
{
return (x(a)==x(b))?(y(a)<y(b)):(x(a)<x(b));
}
void cdq(ll l,ll r)
{
if(l==r) return;
ll mid=(l+r)/2;
for(ll i=l,x=l,y=mid+1;i<=r;i++)
{
if(p[i]<=mid)
{
tmp[x]=p[i]; x++;
}
else
{
tmp[y]=p[i]; y++;
}
}
for(ll i=l;i<=r;i++) p[i]=tmp[i];
cdq(l,mid);
q.clear();
for(ll i=l;i<=mid;i++)
{
while(q.size()>=2&&(y(q.back())-y(q[q.size()-2]))*(x(p[i])-x(q.back()))>=
(y(p[i])-y(q.back()))*(x(q.back())-x(q[q.size()-2])))
q.pop_back();
q.push_back(p[i]);
}
for(ll i=mid+1;i<=r;i++)
{
while(q.size()>=2&&(y(q[1])-y(q.front()))<=k[p[i]]*(x(q[1])-x(q.front())))
q.pop_front();
f[p[i]]=min(f[p[i]],f[q.front()]+t[p[i]]*(c[p[i]]-c[q.front()])+s*(c[n]-c[q.front()]));
}
cdq(mid+1,r);
sort(p+l,p+r+1,cmpx);
}
int main()
{
// #define Isaac
#ifdef Isaac
freopen("in.in","r",stdin);
freopen("out.out","w",stdout);
#endif
cin>>n>>s;
for(ll i=1;i<=n;i++)
{
cin>>t[i]>>c[i]; p[i]=i;
t[i]+=t[i-1]; c[i]+=c[i-1]; k[i]=t[i]+s;
}
for(ll i=1;i<=n;i++) f[i]=t[i]*c[i]+s*c[n];
sort(p+1,p+1+n,cmpk); cdq(1,n);
cout<<f[n]<<endl;
return 0;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...