金发姑娘和N头牛

算法 差分 离散化
发布日期:   2022-01-13
文章字数:   297
阅读次数:  

原题链接

https://www.acwing.com/problem/content/1954/

题目分析

根据题目，把每头奶牛在不同温度下的产奶量列出来，可以构成一个n*T的矩阵，其中n表示奶牛数量，T表示最大温度。
就像下面的矩阵一样。

XXXYYYZZZZ

XXYYYZZZZZ

XYYYYZZZZZ

我们的目标就是要找到和最大的一列的和。

差分算法

因为T比较大，所以直接暴力枚举T肯定是不可行的。观察矩阵可以发现，每一行的值都是三个区间，区间[0,$A_i$-1],[$A_i$,$B_i$],[$B_i$+1,+无穷]，显然可以用差分来表示。

然而传统差分数组不能够表示这么大的温度，所以需要用map来表示差分的值。

时间复杂度

在插入map数组的时候，每次操作消耗$logn$的时间，操作的6n次。
在遍历map数组的时候，由于其有序的性质，只需要n的时间。

最终时间复杂度为$O(nlogn)$

C++ 代码

#include
#include
using namespace std;
map mp;
int main(){
    int n,x,y,z;
    scanf("%d%d%d%d",&n,&x,&y,&z);
    int l,r;
    for(int i=0;imx){
            mx=cur;
        }
    }
    printf("%d\n",mx);
    return 0;
}
文章作者: 青椒
文章链接: https://zhkgo.github.io/2022/01/13/ac1952/
版权声明: 本笔记所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 青椒 !
算法 差分 离散化
 上一篇
c++系统编程复习 c++系统编程复习
Q1 C++静态库和动态库的区别? 静态库是在链接阶段，将汇编生成的目标文件和引用到的库一起链接打包到可执行文件中，而动态库则是在程序运行时才会被载入。 静态库的相关函数库在链接时已经被打包了，所以移植很方便。动态库需要在移植程序时将库文
2022-01-29 青椒
cpp Linux系统编程
下一篇 
欧式空间对齐的迁移学习[论文复现] 欧式空间对齐的迁移学习[论文复现]
前段时间发现华科的迁移学习有点东西，就找了他们的论文来复现一下。《Transfer Learning for Brain-Computer Interfaces: A Euclidean Space Data Alignment Appr
2021-09-28 青椒
迁移学习 论文复现 RSVP
  目录