【二分查找】P11201 [JOIG 2024] たくさんの数字 / Many Digits|普及

本文涉及的基础知识点

本博文代码打包下载
C++二分查找

[JOIG 2024] たくさんの数字 / Many Digits

题目描述

JOI 高中的 Aoi 决定在 $N\times N$ 的表格中写下 $N^2$ 个非负整数。具体地，给定两个长度为 $N$ 的序列 $A,B$，她会在第 $i$ 行第 $j$ 列的格子上写下 $A_i+B_j$。

Aoi 想知道写出这些数需要多少个字符。也就是说，你需要求出写出的 $N^2$ 个整数在十进制下的位数的和。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1,A_2,\dots ,A_N$。

第三行输入 $N$ 个整数 $B_1,B_2,\dots ,B_N$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

3
97 79 7
20 2 21

样例输出 #1

20

样例 #2

样例输入 #2

4
8 97 996 9995
1 2 3 4

样例输出 #2

46

样例 #3

样例输入 #3

1
500000000
500000000

样例输出 #3

10

样例 #4

样例输入 #4

7
436981378 523812834 456708479 413571178 506402783 598271009 523936624
401203104 501634329 506090236 527167431 485527116 439442403 568364549

样例输出 #4

463

提示

【样例解释 #1】

未加粗字体为 Aoi 填写的内容。

例如，第 $1$ 行第 $1$ 列的方格中的整数为 $A_1+B_1=97+20=117$，位数为 $3$。第 $3$ 行第 $2$ 列的方格中的整数为 $A_3+B_2=7+2=9$，位数为 $1$。

$9$ 个数的位数分别为 $3,2,3,2,2,3,2,1,2$，故位数之和为 $3+2+3+2+2+3+2+1+2=20$。

该样例满足子任务 $2,3,8$ 的限制。

【样例解释 #2】

未加粗字体为 Aoi 填写的内容。

例如，第 $2$ 行第 $3$ 列的方格中的整数为 $A_2+B_3=97+3=100$，位数为 $3$。第 $4$ 行第 $2$ 列的方格中的整数为 $A_4+B_2=9995+2=9997$，位数为 $4$。

可以得出答案为 $46$。

该样例满足子任务 $2,6,7,8$ 的限制。

【样例解释 #3】

方格中仅有一个整数 $10^9$，位数为 $10$，故位数之和为 $10$。

该样例满足子任务 $1,2,4,5,8$ 的限制。

【样例解释 #4】

该样例满足子任务 $2,5,8$ 的限制。

【数据范围】

• $1\le N\le 1.5\times 10^5$；
• $1\le A_i\le 999,999,999(1\le i\le N)$；
• $1\le B_j\le 999,999,999(1\le j\le N)$。

【子任务】

1. （$5$ 分）$N=1$；
2. （$11$ 分）$N\le 2000$；
3. （$15$ 分）$A_i\le 2000(1\le i\le N)$，$B_j\le 2000(1\le j\le N)$；
4. （$8$ 分）$10^8\le A_i\le 5\times 10^8(1\le i\le N)$，$10^8\le B_j\le 5\times 10^8(1\le j\le N)$；
5. （$22$ 分）$10^8\le A_i(1\le i\le N)$，$10^8\le B_j(1\le j\le N)$；
6. （$12$ 分）$A_i\le 1.5\times 10^5(1\le i\le N)$，$B_j=j(1\le j\le N)$；
7. （$13$ 分）$B_j=j(1\le j\le N)$；
8. （$14$ 分）无附加限制。

二分查找

对a，排序。
通过ib 枚举b。
和ib组成的项，i位数及以下的数量c[i]：
$$\{\begin{array}{ll}a.lower(10^i-ib{)}_a.begin()& i\in [1,9]\\ 0& i==0\\ a.size()& i==10\end{array}$$

代码

核心代码

#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 <bitset>
using namespace std;



template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {
	vector<T> ret(n);
	for(int i=0;i<n;i++) {
		scanf(pFormat, &ret[i]);	
	}
	return ret;
}

template<class T = int>
vector<T> Read( const char* pFormat = "%d") {
	int n;
	scanf("%d", &n);
	vector<T> ret;
	T d;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

string ReadChar(int n) {
	string str;
	char ch;
	while (n--) {
		do
		{
			scanf("%c", &ch);
		} while (('\n' == ch));
			str += ch;
	}
	return str;
}
template<class T1,class T2>
void ReadTo(pair<T1, T2>& pr) {
	cin >> pr.first >> pr.second;
}

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:
	long long Ans(vector<int>& a, vector<int>& b) {
		const int N = a.size();
		sort(a.begin(), a.end());
		long long ans = 0;
		for (const auto& ib : b) {
			int cnt[11] = { 0 };
			cnt[10] = a.size();
			int mul = 1;
			for (int i = 1; i < 10; i++) {
				mul *= 10;
				cnt[i] = lower_bound(a.begin(), a.end(), mul - ib) - a.begin();
			}
			for (long long i = 1; i <= 10; i++) {
				ans += (cnt[i] - cnt[i - 1]) * i;
			}
		}
		return ans;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	int n;	
	cin >> n ;
	auto a = Read<int>(n);
	auto b = Read<int>(n);
	
#ifdef _DEBUG		
	Out(a, "a=");
	Out(b, ",b=");
#endif	
	auto res = Solution().Ans(a,b);
	cout << res << endl;		
	return 0;
}

单元测试

TEST_METHOD(TestMethod11)
		{	
			a = { 97,79,7 }, b = { 20,2,21 };
			auto res = Solution().Ans(a,b);
			AssertEx(20LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			a = { 8,97,996,9995 }, b = { 1,2,3,4 };
			auto res = Solution().Ans(a, b);
			AssertEx(46LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			a = { 500000000 }, b = { 500000000 };
			auto res = Solution().Ans(a, b);
			AssertEx(10LL, res);
		}
		TEST_METHOD(TestMethod14)
		{
			a = { 436981378,523812834,456708479,413571178,506402783,598271009,523936624 }, b = { 401203104,501634329,506090236,527167431,485527116,439442403,568364549 };
			auto res = Solution().Ans(a, b);
			AssertEx(463LL, 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++**实现。