这段时间要沉迷刷题一段时间了,就让CSDN陪我一起吧!
一、题目大意
题目的大致意思是,给你一个位数为l的整数,要求将这个整数分为连续的两个部分,使得这两个分出来的整数加和最小,而且分出的两个数字都不可以包含前导零。
二、题目思路以及AC代码
这题其实思路很简单,但就是在实现代码的时候需要注意一点。
首先,肯定不能直接暴力的,l的范围是1e5,直接暴力每个分点的话,则需要1e5次循环,然后 在每次循环中要计算两个高精度加法,也是1e5的复杂度,相乘是1e10的复杂度,2s的时间也是很悬的。
所以我们要考虑简单的方法,题目要求加和最小,那么如何选择切点才能使两个子串的加和最小呐?肯定是优先从中间选,因为这样限制了他的位权最小,这里我无法给出严格的证明,但是,我可以用一个极端的例子来为你解释。
比如一个数a1a2…al,我们从中间切分,假设l是偶数,那么切分出了两个数为a1a2…al/2和al/2+1al/2+2…al,这是我们从中间切分的结果,那如果不从中间切分,而是偏离一点呢?切出来的结果就是a1a2…al/2+1和al/2+2al/2+3…al,现在,我们就想办法给这些a赋值,使前一种分法加和尽可能大,后一种分法加和尽可能小。
那么我们就需要使a1 - al/2尽可能小,因为后一种分法增加了其位权,使al/2+1 - al尽可能大,所以我们就构造出来了一个定性的证明结果,这个数是1000…0099999999,通过这个结果,我们可以发现,从中间切分会使加和最小。
所以我们的思路就比较清晰了,从中间向两边扩散,直到找到一个不含前导零的最小加和的分法为止,就是我们要的最终答案。
下面给出AC代码,62ms,2196KB:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155#include <iostream> #include <string> #include <cstring> #include <algorithm> using namespace std; struct BigInteger { int digits[100010]; int size; void init() { for (int i = 0; i < 100010; i++) { digits[i] = 0; } size = 0; } void setup(string x) { init(); int len = x.length(); for (int i = len - 1; i >= 0; i--) { digits[size++] = x[i] - '0'; } } BigInteger split(int begin, int end) { BigInteger c; c.init(); for (int i = begin; i <= end; i++) { c.digits[c.size++] = digits[i]; } return c; } BigInteger operator + (const BigInteger& A) { BigInteger c; c.init(); int carry = 0; int len = max(A.size, size); for (int i = 0; i < len; i++) { int tmp = A.digits[i] + digits[i] + carry; c.digits[c.size++] = tmp % 10; carry = tmp / 10; } if (carry) c.digits[c.size++] = carry; return c; } bool operator > (const BigInteger& A) { if (A.size > size) return false; if (A.size < size) return true; for (int i = size - 1; i >= 0; i--) { if (A.digits[i] > digits[i]) return false; if (A.digits[i] < digits[i]) return true; } return false; } void print() { for (int i = size - 1; i >= 0; i--) { cout << digits[i]; } cout << endl; } }; int l; string str; int main() { cin >> l >> str; BigInteger a; a.setup(str); BigInteger ans; int point = l / 2; if (l & 1) { for (int i = 0; i <= point; i++) { int first = point - i; int second = point + 1 + i; if (first == 0) { ans = a; break; } if (!a.digits[first - 1] && !a.digits[second - 1]) continue; BigInteger f, s; f.init(); s.init(); if (a.digits[first - 1]) f = a.split(0, first - 1) + a.split(first, l - 1); if (a.digits[second - 1]) s = a.split(0, second - 1) + a.split(second, l - 1); if (!f.size) { ans = s; break; } if (!s.size) { ans = f; break; } if (f > s) ans = s; else ans = f; break; } } else { for (int i = 0; i <= point; i++) { int first = point - i; int second = point + i; if (first == 0) { ans = a; break; } if (!a.digits[first - 1] && !a.digits[second - 1]) continue; BigInteger f, s; f.init(); s.init(); if (a.digits[first - 1]) f = a.split(0, first - 1) + a.split(first, l - 1); if (a.digits[second - 1]) s = a.split(0, second - 1) + a.split(second, l - 1); if (!f.size) { ans = s; break; } if (!s.size) { ans = f; break; } if (f > s) ans = s; else ans = f; break; } } ans.print(); return 0; }
如果有问题,欢迎大家指正!!!
最后
以上就是欣慰鸵鸟最近收集整理的关于【思维题】CodeForce 1182B Split a Number的全部内容,更多相关【思维题】CodeForce内容请搜索靠谱客的其他文章。
发表评论 取消回复