P4480-[BJWC2018]餐巾计划问题【三分,贪心】
2024-09-02 22:05:24
正题
题目链接:https://www.luogu.com.cn/problem/P4480
题目大意
\(n\)天,第\(i\)天需要\(a_i\)个餐巾。
每个餐巾价格为\(p\),使用完后有两种清洗方法
- 清洗\(m_1\)天,费用为\(c_1\)
- 清洗\(m_2\)天,费用为\(c_2\)
求满足所有需求的最小花费
\(1\leq n\leq 2\times 10^5,1\leq m_1,m_2\leq n,1\leq c_1,c_2,a_i\leq 100\)
解题思路
如果固定了购买的毛巾数量那么此题就有一个贪心的做法。
首先先把购买的全部优先使用了
然后如果快的那个洗法费用更低,那么显然全部用快的洗法。
否则就是一个快但是贵,一个慢但是便宜。那么我们的决策就是能用慢的就不使用快的。这个可以用决策后延来解决,当我们需要毛巾的时候再决定前面的毛巾的洗法。
这样的贪心是\(O(n)\)的,但是我们不能暴力枚举毛巾数量。
感性理解的话不难费用根据毛巾的数量呈一个单谷状,所以我们可以直接三分出这个谷底即可。
时间复杂度\(O(n\log (100n))\),因为\(deque\)比较慢所以我的标要开\(\text{-O2}\)才能过/kk
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+10,inf=2e9;
int n,p,m1,m2,c1,c2,w[N];
struct node{
int t,w;
node(int tt=0,int ww=0)
{t=tt;w=ww;return;}
};
deque<node> q1,q2,q3;
int calc(int x){
int ans=x*p;
q1.clear();q2.clear();q3.clear();
for(int i=1;i<=n;i++){
while(!q1.empty()&&q1.front().t+m1<=i)
q2.push_back(q1.front()),q1.pop_front();
while(!q2.empty()&&q2.front().t+m2<=i)
q3.push_back(q2.front()),q2.pop_front();
int v=w[i],tmp=min(v,x);x-=tmp;v-=tmp;
while(v&&!q3.empty()){
tmp=min(v,q3.back().w);
v-=tmp;ans+=tmp*c2;
if(tmp==q3.back().w)q3.pop_back();
else q3.back().w-=tmp;
}
while(v&&!q2.empty()){
tmp=min(v,q2.back().w);
v-=tmp;ans+=tmp*c1;
if(tmp==q2.back().w)q2.pop_back();
else q2.back().w-=tmp;
}
if(v)return inf;
q1.push_back(node(i,w[i]));
}
return ans;
}
int main()
{
scanf("%d%d%d%d%d%d",&n,&m1,&m2,&c1,&c2,&p);
if(m1>m2)swap(m1,m2),swap(c1,c2);
if(c1<c2)c2=c1,m2=m1;
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
int l=1,r=n*100;
while(l<=r){
int mid=(l+r)>>1;
if(calc(mid)<calc(mid+1))r=mid-1;
else l=mid+1;
}
printf("%d\n",calc(l));
return 0;
}
最新文章
- CSS学习笔记——视觉格式化模型 visual formatting model
- android开发中使不同的listview同时联动
- 突如其来的";中断异常";,我(Java)该如何处理?
- Serial Port Programming on Linux(转载)
- List和Dictionary泛型类查找效率浅析
- LeetCode&mdash;&mdash;Single Number(找出数组中只出现一次的数)
- shell基础
- 使用adb shell dumpsys检测Android的Activity任务栈
- [ZOJ 1011] NTA (dfs搜索)
- Android Service实时向Activity传递数据
- .net core 1.1.0 MVC 控制器接收Json字串 (JObject对象) (二)
- Linux命令: ln
- 庞玉栋:浅谈seo优化对于网站建设的重要性
- Java Byte取值范围
- 使用原生php读写excel文件
- [机器学习Lesson3] 梯度下降算法
- 反射模拟DbUtils实现ResultSet转成Bean实例
- jdbc,mysql 数据库BLOB返回值 [B 的问题
- 学习笔记TF015:加载图像、图像格式、图像操作、颜色
- enq: FB - contention