手机网站被劫持怎么办怎么解决_海口疫情最新消息今天_seo公司后付费_十大营销策略有哪些

本文涉及的基础知识点

C++二分查找
树状数组 离散化
本博文代码打包下载

[yLCPC2024] C. 舞萌基本练习

题目描述

扶苏在游玩舞萌 dx 的过程中，发现一首歌可以分成不超过 $k$ 段分别进行练习。

具体来说，这首歌共有 $n$ 个音符，每个音符有一个难度值。第 $i$ 个音符的难度值为 $a_i$。扶苏觉得一段歌曲的音符的难度应该是尽可能变难的。因此对于音符序列的一个区间 $[l,r]$，她认为这段区间的『不优美度』是这段区间的逆序对数。

一个区间 $[l,r]$ 的逆序对数被定义为满足 $l\le i<j\le r$ 且 $a_i>a_j$ 的数对 $(i,j)$ 个数。

扶苏希望把这首歌划分成不超过 $k$ 个子段，满足每个音符都至少属于一个子段，使得不优美度最大的段的不优美度尽可能小。

形式化的，你需要划分出 $t\le k$ 个区间 $[l_1,r_1],[l_2,r_2],\dots [l_t,r_t]$，满足：

• $l_1=1$，$r_t=n$。
• 对 $1\le i<t$，$r_i+1=l_{i+1}$。
• 对 $1\le i\le t$，$l_i\le r_i$。

定义 $f(l,r)$ 表示区间 $[l,r]$ 的不优美度，最小化 $\underset{i=1}{\overset{t}{\max }}f(l_i,r_i)$

输入格式

本题单个测试点内有多组测试数据。第一行是一个正整数 $T$，表示数据组数。对每组数据：

第一行是两个整数 $n,k$（$1\le k\le n\le 10^5$），表示歌曲的音符数和最多的划分段数。
第二行有 $n$ 个整数 $a_1,a_2,\dots ,a_n$（$-10^9\le a_i\le 10^9$），表示每个音符的难度。

数据保证单个测试点内的 $n$ 之和不超过 $10^5$。

输出格式

对每组数据，输出一行一个整数表示答案。

样例 #1

样例输入 #1

2
5 2
1 3 2 5 4
8 2
4 2 3 6 7 1 8 5

样例输出 #1

1
2

离散化+二分查找+树状数组

本题只关心相对大小，不关心具体值。所以可以离散化，即最小值0，次小值1$\cdots$
二分查找类型：寻找首端
参数类型long long,范围[0,N*N]
检测函数：
第一个区间left等于0，其它区间left等于上一个区间r。
r等于N，则[left,r)是一个合法区间。
a[left…r]的逆序对大于mid，是一个区间。
计算完区间，依次做两个判断：
r == N。返回真
区间数> k，返回假。
时间复杂度：O(Tlog(NN)n)

代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) ;return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;scanf("%d", &n);vector<T> ret(n);for(int i=0;i < n ;i++) {cin >> ret[i];}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 12 * 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;}inline void write(char ch){*m_p++ = ch;}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);}
private:char  puffer[N], * m_p;
};template<int N = 12 * 1'000'000>
class CInBuff
{
public:inline CInBuff() {fread(buffer, 1, N, stdin);}inline int Read() {int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);return f ? -x : x;}
private:char buffer[N], * S = buffer;
};class CDiscretize //离散化
{
public:CDiscretize(vector<int> nums){sort(nums.begin(), nums.end());nums.erase(std::unique(nums.begin(), nums.end()), nums.end());m_nums = nums;for (int i = 0; i < nums.size(); i++){m_mValueToIndex[nums[i]] = i;}}int operator[](const int value)const{auto it = m_mValueToIndex.find(value);if (m_mValueToIndex.end() == it){return -1;}return it->second;}int size()const{return m_mValueToIndex.size();}vector<int> m_nums;
protected:unordered_map<int, int> m_mValueToIndex;
};template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex, INDEX_TYPE tol = 1) :m_iMin(iMinIndex), m_iMax(iMaxIndex), m_iTol(tol) {}template<class _Pr>INDEX_TYPE FindFrist(_Pr pr){auto left = m_iMin - m_iTol;auto rightInclue = m_iMax;while (rightInclue - left > m_iTol){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd(_Pr pr){INDEX_TYPE leftInclude = m_iMin;INDEX_TYPE right = m_iMax + m_iTol;while (right - leftInclude > m_iTol){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax, m_iTol;
};template<class ELE = int >
class CTreeArr
{
public:CTreeArr(int iSize) :m_vData(iSize + 1){}void Add(int index, ELE value){if ((index < 0) || (index >= m_vData.size() - 1)) { return; }index++;while (index < m_vData.size()){m_vData[index] += value;index += index & (-index);}}ELE Sum(int index)//[0...index]之和{index++;ELE ret = 0;while (index){ret += m_vData[index];index -= index & (-index);}return ret;}ELE Sum() { return Sum(m_vData.size() - 2); }ELE Get(int index){return Sum(index) - Sum(index - 1);}
private:vector<ELE> m_vData;
};//P10235 [yLCPC2024] C. 舞萌基本练习
class Solution {public:long long Ans(const int K ,vector<int>& a) {const int N = a.size();CDiscretize dis(a);vector<int> b;for (const auto& i : a) {b.emplace_back(dis[i]);}auto Check = [&](long long mid) {int rc = 0;CTreeArr<long long> tree(N);for (int left = 0, r = 0; left < N; ) {						long long cnt = 0;auto Cnt = [&]() {return tree.Sum() - tree.Sum(b[r]);};while ((r < N) && (cnt + Cnt() <= mid)) {cnt += Cnt(); tree.Add(b[r], 1); r++;}for (; left < r; left++) {tree.Add(b[left], -1);}rc++;						}return rc <= K;};return CBinarySearch<long long>(0, (long long)N * N).FindFrist(Check);}};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	int T, n,k;cin >> T;COutBuff<23*100'000> ob;for (int i = 0; i < T; i++) {cin >> n >> k;auto a = Read<int>(n);auto res = Solution().Ans(k, a);ob.write(res);ob.write('\n');}	ob.ToFile();
#ifdef _DEBUG		/*printf("k=%d", k);Out(a, ",a=");*/
#endif // DEBUG	return 0;
}

单元测试

vector<int> a;int k;TEST_METHOD(TestMethod11){k = 2, a = { 1,3,2,5,4 };auto res = Solution().Ans(k,a);AssertEx(1LL, res);}TEST_METHOD(TestMethod12){k = 2, a = { 4,2,3,6,7,1,8,5 };auto res = Solution().Ans(k, a);AssertEx(2LL, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。