【二分查找】P11201 [JOIG 2024] たくさんの数字 / Many Digits|普及 - ToB企服应用市场:ToB评测及商务社交产业平台

#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(20
LL, res); } TEST_METHOD(TestMethod12) { a = { 8,97,996,9995 }, b = { 1,2,3,4 }; auto res = Solution().Ans(a, b); AssertEx(46
LL, res); } TEST_METHOD(TestMethod13) { a = { 500000000 }, b = { 500000000 }; auto res = Solution().Ans(a, b); AssertEx(10
LL, res); } TEST_METHOD(TestMethod14) { a = { 436981378,523812834,456708479,413571178,506402783,5982710
09,523936624 }, b = { 40120
310
4,501634329,506090236,527167431,485527116,439442403,568364549 }; auto res = Solution().Ans(a, b); AssertEx(46
3LL, res); }

复制代码