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

空调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每个位置的操作


http://www.kler.cn/a/586705.html

相关文章:

  • C++移动语义与右值引用:从理论到实践的深度解析引言
  • python:数据类构建器
  • 《DeepSeek深度使用教程:开启智能交互新体验》Deepseek深度使用教程
  • 【大模型基础_毛玉仁】2.4 基于 Encoder-Decoder 架构的大语言模型
  • AtCoder Beginner Contest 003(A - 社の給料、B -トランプ、C -プログラミング講座、D - 社の冬 )题目讲解
  • 【PHP】新版本特性记录(持续更新)
  • java 的标记接口RandomAccess使用方法
  • vulnhub靶场之stapler靶机
  • MIDI,AI 3D场景生成技术
  • Audacity 技术浅析(一)
  • [CISSP] [3] 人员安全与社会工程
  • 原生微信小程序实现导航漫游(Tour)
  • 农作物病害数据集
  • 性能优化:javascript 如何检测并处理页面卡顿
  • A SURVEY ON POST-TRAINING OF LARGE LANGUAGE MODELS——大型语言模型的训练后优化综述——第2部分
  • 模型评估指标详解:分类与回归场景
  • 基于SpringBoot+Vue的毕业论文管理系统+LW示例参考
  • 【NLP】 5. Word Analogy Task(词类比任务)与 Intrinsic Metric(内在度量)
  • 微信小程序面试内容整理-JSON
  • 【c++】【线程】【信号量】三个线程顺序打印1--100