免费收录链接网_如何维护公司网站_湖南靠谱的关键词优化哪家好_网站综合排名信息查询

本文涉及的基础知识点

C++二分查找
C++差分数组
【C++】树状数组的使用、原理、封装类、样例

P6172 [USACO16FEB] Load Balancing P

题目背景

本题与银组同名题目在题意上一致，唯一的差别是数据范围。

题目描述

Farmer John 的 $N$ 头奶牛（ $\leq N \leq 10^5$ ）散布在整个农场上。整个农场是一个无限大的二维平面，第 $i$ 头奶牛的坐标是 $x_i,y_i)$ （保证 $x_i,y_i$ 均为正奇数，且 $x_i,y_i \leq 10^6$ ），且没有任意两头奶牛在同一位置上。

FJ 希望修建一条竖直方向的栅栏，它的方程是 $x = a$ ，他还希望修建一条水平方向的栅栏，它的方程是 $y = b$ 。为了防止栅栏经过奶牛， $a, b$ 均要求是偶数。容易发现，这两个栅栏会在 $(a, b)$ 处相交，将整个农场分割为四个区域。

FJ 希望这四个区域内的奶牛数量较为均衡，尽量避免一个区域奶牛多而另一个区域奶牛少的情况。令 $M$ 为四个区域里奶牛最多区域的奶牛数量，请帮 FJ 求出 $M$ 的最小值。

输入格式

第一行一个整数 $N$ 。

接下来 $N$ 行，每行两个整数 $x_i,y_i$ ，描述第 $i$ 头奶牛的位置。

输出格式

输出 $M$ 的最小值。

输入输出样例 #1

输入 #1

输出 #1

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

各点按x升序排序，对y离散化（y的最小值改成0，次小值改成1…）
枚举a，计算b。x <=a的奶牛在左边，用树状数组实现的差分数组diff1记录；x>a的奶牛在右边，用diff2记录。a 从a1迭代a2时，任意(a2,y)都：
diff1[y]++ ,diff2[y]–。
针对每个a，进行二分：
二分类型：寻找首端。
参数范围：[0,Y]
检测函数逻辑：[0,a]包括a，是左边；其余是右边。[0,b]是上边，其余是下边。
M1，M2,M3,M4是左上，右上，左下，右下的奶牛数。
检测函数返回：max(M1,M2) >= max(M3,M4)
如果二分函数的返回值是：b1，则只需要考虑b1和b1-1。

代码

核心代码

#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;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}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 = 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;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class KMP
{
public:virtual int Find(const string& s, const string& t){CalLen(t);for (int i1 = 0, j = 0; i1 < s.length(); ){for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++);//i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等//t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2)if (0 == j){i1++;continue;}const int i2 = i1 + j;j = m_vLen[j - 1];i1 = i2 - j;//i2不变}return -1;}//vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性 部分m_vSameLen[i]会缺失//static vector<int> Next(const string& s)//{// j = vNext[i] 表示s[0,i]的最大公共前后缀是s[0,j]//	const int len = s.length();//	vector<int> vNext(len, -1);//	for (int i = 1; i < len; i++)//	{//		int next = vNext[i - 1];//		while ((-1 != next) && (s[next + 1] != s[i]))//		{//			next = vNext[next];//		}//		vNext[i] = next + (s[next + 1] == s[i]);//	}//	return vNext;//}const vector<int> CalLen(const string& str){m_vLen.resize(str.length());for (int i = 1; i < str.length(); i++){int next = m_vLen[i - 1];while (str[next] != str[i]){if (0 == next){break;}next = m_vLen[next - 1];}m_vLen[i] = next + (str[next] == str[i]);}return m_vLen;}
protected:int m_c;vector<int> m_vLen;//m_vLen[i] 表示str[0,i]的最长公共前后缀的长度
};template<long long MOD = 1000000007, class T1 = int, class T2 = long long>
class C1097Int
{
public:C1097Int(T1 iData = 0) :m_iData(iData% MOD){}C1097Int(T2 llData) :m_iData(llData% MOD) {}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((T2)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((T2)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = ((T2)MOD + m_iData - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int(((T2)MOD + m_iData - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((T2)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((T2)m_iData * o.m_iData) % MOD;return *this;}C1097Int  operator/(const C1097Int& o)const{return *this * o.PowNegative1();}C1097Int& operator/=(const C1097Int& o){*this /= o.PowNegative1();return *this;}bool operator==(const C1097Int& o)const{return m_iData == o.m_iData;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(T2 n)const{C1097Int iRet = (T1)1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}T1 ToInt()const{return ((T2)m_iData + MOD) % MOD;}
private:T1 m_iData = 0;;
};template<class T = int>
class CDiscretize //离散化
{
public:CDiscretize(vector<T> 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 T 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<T> m_nums;
protected:unordered_map<T, int> m_mValueToIndex;
};template<class ELE = int >
class ITreeArrSumOpe
{
public:virtual void Assign(ELE& dest, const ELE& src) = 0;virtual ELE Back(const ELE& n1, const ELE& n2) = 0;
};template<class ELE = int >
class CTreeArrAddOpe :public ITreeArrSumOpe<ELE>
{
public:virtual void Assign(ELE& dest, const ELE& src) {dest += src;}virtual ELE Back(const ELE& n1, const ELE& n2) {return n1 - n2;}
};template<class ELE = int, class ELEOpe = CTreeArrAddOpe<ELE> >
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_ope.Assign(m_vData[index], value);index += index & (-index);}}ELE Sum(int index)//[0...index]之和{index++;ELE ret = 0;while (index){m_ope.Assign(ret, m_vData[index]);index -= index & (-index);}return ret;}ELE Sum() { return Sum(m_vData.size() - 2); }ELE Get(int index){return m_ope.Back(Sum(index), Sum(index - 1));}
private:ELEOpe m_ope;vector<ELE> m_vData;
};
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;
};class Solution {
public:int Ans(vector<pair<int, int>>& pts) {const int N = pts.size();sort(pts.begin(), pts.end());vector<int> ys;for (const auto& [x, y] : pts) {ys.emplace_back(y);}CDiscretize dis(ys);for (auto& [x, y] : pts) {y = dis[y];}const int M = dis.size();CTreeArr<int> diff1(M), diff2(M);for (const auto& [x, y] : pts) {diff2.Add(y, 1);}int ans = INT_MAX / 2;for (int i = 0; i < N; i++) {auto Check = [&](int mid) {const int M1 = diff1.Sum(mid);const int M2 = diff2.Sum(mid);const int M3 = i - M1;const int M4 = (N - i) - M2;return max(M1, M2) > max(M3, M4);};auto CalMax = [&](int mid) {const int M1 = diff1.Sum(mid);const int M2 = diff2.Sum(mid);const int M3 = i - M1;const int M4 = (N - i) - M2;return max(max(M1, M2), max(M3, M4));};int b = CBinarySearch<int>(0, M - 1).FindFrist(Check);ans = min(ans, CalMax(b));ans = min(ans, CalMax(b - 1));diff1.Add(pts[i].second, 1);diff2.Add(pts[i].second, -1);while ((i + 1 < N) && (pts[i].first == pts[i + 1].first)) {i++;diff1.Add(pts[i].second, 1);diff2.Add(pts[i].second, -1);}}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);int n;cin >> n     ;auto pts = Read<pair<int,int>>(n);	
#ifdef _DEBUG		//printf("M=%d,K=%d",m, k);Out(pts, ",pts=");//Out(edge, ",edge=");/*Out(que, "que=");*/
#endif // DEBUG	auto res = Solution().Ans(pts);	cout << res << "\n";return 0;
}

单元测试

vector<pair<int, int>> pts;TEST_METHOD(TestMethod1){pts = { {7,3},{5,5},{7,13},{3,1},{11,7},{5,3},{9,1} };auto res = Solution().Ans(pts);AssertEx(2, 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++**实现。

免费收录链接网_如何维护公司网站_湖南靠谱的关键词优化哪家好_网站综合排名信息查询

本文涉及的基础知识点

P6172 [USACO16FEB] Load Balancing P

题目背景

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

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

代码

核心代码

单元测试

扩展阅读

视频课程

测试环境

最新新闻

热搜词

免费收录链接网_如何维护公司网站_湖南靠谱的关键词优化哪家好_网站综合排名信息查询

本文涉及的基础知识点

P6172 [USACO16FEB] Load Balancing P

题目背景

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

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

代码

核心代码

单元测试

扩展阅读

视频课程

测试环境

最新新闻

热搜词

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