空调acwing二进制差分
题目:
4889. 空调II
- 题目
- 提交记录
- 讨论
- 题解
- 视频讲解
炎炎夏日,酷热难耐,农夫约翰计划打开牛棚中的空调给奶牛降温。
约翰的牛棚中一共有 N𝑁 头奶牛,编号 1∼N1∼𝑁。
牛棚中有 100100 个牛栏排成一排,编号依次为 1∼1001∼100。
每头奶牛都占据着连续若干个牛栏,同一个牛栏最多被一头奶牛占据。
第 i𝑖 头奶牛占据的牛栏范围是 [si,ti][𝑠𝑖,𝑡𝑖]。
不同奶牛的降温需求不同,第 i𝑖 头奶牛的降温需求为 ci𝑐𝑖,这意味着它占据的每个牛栏都至少需要降温 ci𝑐𝑖。
牛棚中一共有 M𝑀 台空调,编号 1∼M1∼𝑀。
第 i𝑖 台空调的运行成本为 mi𝑚𝑖,开启这台空调可以让 [ai,bi][𝑎𝑖,𝑏𝑖] 范围内的每个牛栏降温 pi𝑝𝑖。
不同空调的覆盖范围可能重叠,降温效果也可以叠加。
约翰希望在让所有奶牛的降温需求都得到满足的前提下,花费的总成本尽可能小。
数据保证:至少存在一组方案满足所有奶牛的降温需求。
输出所需总成本的最小可能值。
输入格式
第一行包含 N,M𝑁,𝑀。
接下来 N𝑁 行,每行包含三个整数 si,ti,ci𝑠𝑖,𝑡𝑖,𝑐𝑖。
接下来 M𝑀 行,每行包含四个整数 ai,bi,pi,mi𝑎𝑖,𝑏𝑖,𝑝𝑖,𝑚𝑖。
输出格式
一个整数,表示所需总成本的最小可能值。
数据范围
1≤N≤201≤𝑁≤20,
1≤M≤101≤𝑀≤10,
1≤si≤ti≤1001≤𝑠𝑖≤𝑡𝑖≤100,
1≤ci≤1061≤𝑐𝑖≤106,
1≤ai≤bi≤1001≤𝑎𝑖≤𝑏𝑖≤100,
1≤pi≤1061≤𝑝𝑖≤106,
1≤mi≤10001≤𝑚𝑖≤1000
输入样例:
2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5
输出样例:
10
样例解释
一种满足条件的最佳方案为运行第 1,3,41,3,4 个空调,所需成本为 3+2+5=103+2+5=10。
代码:
#include<bits/stdc++.h>
using namespace std;
const int M=11,temp=110;
const int INF = 0x3f3f3f3f;
int cow[temp],air[temp];//两个数组存当前位置栏的温度
int R=-INF;
struct RangeAir{
int l,r,p,m;
}range[M];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int s,t,c;
cin>>s>>t>>c;
for(int j=s;j<=t;j++){
cow[j]=max(cow[j],c);//更新每个区间栏的温度,存最大的就行,满足最大就都满足了
}
R=max(R,t);//R方便后续求air原数组时的遍历长度
}
//输入空调
for(int i=1;i<=m;i++){
cin>>range[i].l>>range[i].r>>range[i].p>>range[i].m;
}
int res=INF;
for(int i=1;i<1<<m;i++){//暴力遍历每一种方案,哪个位置空调选,哪个位置不选
//i<不是<=,<=就多了一个位置了 eg:m=4,如果i取16的话,二进制为10000,多了一个位置的空调,只枚举四个位置上的空调就行
bool flag=true;//记录当前方案所选位置的空调是否满足奶牛的温度
memset(air,0,sizeof(air));
int k=i;
int cost=0;
for(int j=1;j<=m;j++){
if(k&1){//如果当前位置空调选中,则进行差分操作
air[range[j].l]+=range[j].p;
air[range[j].r+1]-=range[j].p;
cost+=range[j].m;
}
k>>=1;//遍历下一个位置的空调,同时j++
}
//用差分算出原数组
for(int j=1;j<=R;j++){
air[j]+=air[j-1];
if(air[j]<cow[j]) {
flag=false;
break;//小于不满足,遍历下一次的方案
}
}
if(flag){
res=min(res,cost);
}
}
cout<<res;
return 0;
}
解析:
我首先想到的是差分,(每段区间加上一个相同的值,不过我是想的用一个数组,先存入每个位子要满足的温度,在进行m次差分,区间减去一个数。开两个数组更方便)cow存栏位置需要的温度,air存每个位置的空调可以操作的温度,每次房案计算时对比就好
暴力枚举所有方案,因为每个位置上的空调只有选和不选两种方案,所以采用二进制枚举遍历的方法,罗列每一种方案,如果该位置为1则进行差分操作
时间复杂度o(2^m*m)
2^m枚举所有方案
m每个位置的操作