首页 > 分享 > 花期内花的数目【离散化+前缀和+差分】

花期内花的数目【离散化+前缀和+差分】

花匠小妙招
2024-08-14 02:49

题目是290场周赛T4花期内花的数目
在这里插入图片描述
一般讲出生、上下车这种一上一下的情况，很大可能是使用差分数组，关于差分数组的使用，建议去看以下链接：差分 --算法竞赛专题解析
本题具体思路如下：

离散化思想：对于花期在[start,end]的花朵，我们看成是将区间[start,end]上的每个时间点都增加一朵花。对于第i个人，我们只需要计算出在personi时间结点的花朵数量即可差分：构建差分数组map<int,int>m，对于每个区间[start,end]，我们想要将区间里面所有的值加1，因此修改差分数组：m[start]+1，m[end+1]-1；我们得到一些键值对(key,value)，前者指示区间的边界，后者指示对区间的值的修改，由于最大的区间能达到109，因此一个一个从0到最大区间，每个值都构造答案数组不行，我们只考虑我们需要考虑的personi前缀和：我们使用前缀和的思想，由于map是已经排好序的，我们只需要遍历map，将所有value相加，将前缀和的值更新到map的value中，得到的键值对为(key,sum(value))二分：对于每个答案的personi，使用二分查找第一个比它小的下标即可

vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) { vector<int>ans; map<int,int>m; //差分数组 for(auto& f:flowers){ int start=f[0]; int end=f[1]; m[start]++; //差分化 m[end+1]--; } vector<int>res; //记录出现在map中的区间边界值 res.push_back(0); int sum=0; //前缀和 for(auto& x:m){ int a1=x.first; m[a1]+=sum; sum=m[a1]; res.push_back(a1); } for(auto& p:persons){ int pos=upper_bound(res.begin(),res.end(),p)-res.begin()-1; //查找第一个比他小的下标 ans.push_back(m[res[pos]]); } return ans; }

123456789101112131415161718192021222324

网址: 花期内花的数目【离散化+前缀和+差分】 https://m.huajiangbk.com/newsview17711.html

所属分类：花卉