当前位置：首页 > article >正文

空调acwing二进制差分

article 2025/3/16 8:35:42

题目：

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

输入样例：

输出样例：

样例解释

一种满足条件的最佳方案为运行第 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则进行差分操作