【二分查找】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】

$+$	$\text{20}$	$\text{2}$	$\text{21}$
$\text{97}$	$117$	$99$	$118$
$\text{79}$	$99$	$81$	$100$
$\text{7}$	$27$	$9$	$28$

未加粗字体为 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】

$+$	$\text{1}$	$\text{2}$	$\text{3}$	$\text{4}$
$\text{8}$	$9$	$10$	$11$	$12$
$\text{97}$	$98$	$99$	$100$	$101$
$\text{996}$	$997$	$998$	$999$	$1000$
$\text{9995}$	$9996$	$9997$	$9998$	$9999$

未加粗字体为 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 _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUGint 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++**实现。