P8598 [蓝桥杯 2013 省 AB] 错误票据

[蓝桥杯 2013 省 AB] 错误票据

题目背景

某涉密单位下发了某种票据，并要在年终全部收回。

题目描述

每张票据有唯一的 ID 号，全年所有票据的 ID 号是连续的，但 ID 的开始数码是随机选定的。因为工作人员疏忽，在录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号。

你的任务是通过编程，找出断号的 ID 和重号的 ID。

数据保证断号不可能发生在最大和最小号。

输入格式

一个整数 $N(N<100)$ 表示后面数据行数，接着读入 $N$ 行数据，每行数据长度不等，是用空格分开的若干个（不大于 $100$ 个）正整数（不大于 $10^5$），每个整数代表一个 ID 号。

输出格式

要求程序首先输入要求程序输出 $1$ 行，含两个整数 $m$，$n$，用空格分隔，其中，$m$ 表示断号 ID，$n$ 表示重号 ID。

样例 #1

样例输入 #1

2
5 6 8 11 9
10 12 9
1
2
3

样例输出 #1

7 9
1

样例 #2

样例输入 #2

6
164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
172 189 127 107 112 192 103 131 133 169 158
128 102 110 148 139 157 140 195 197
185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119
1
2
3
4
5
6
7

样例输出 #2

105 120
1

Java代码一

import java.util.*;
class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s[] = new int[10000];
        int cnt = 0;
        while(sc.hasNext())
        {
           s[cnt++]=sc.nextInt();
        }
        Arrays.sort(s,0,cnt);
        int a=0,b=0;
        for(int i=0;i<cnt-1;i++)
        {
            if(s[i]+2==s[i+1])
                a=s[i]+1;
            if(s[i]==s[i+1])
                b=s[i];
        }
        System.out.println(a+" "+b);
    }
}
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

这个是我第一次写的代码，没有想到解决该题输入方式的办法，但也在官网成功 $AC$ ，然后在 $CSDN$ 搜了一下题解，看到了

JAVA算法练习（5）：错误票据

这篇文章，文章很详细的讲解了如何解决这个问题，我根据这篇文章写了如下代码

Java代码二

import java.util.*;
class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        ArrayList<Integer> s = new ArrayList();
        String str = "";
        while(n-->0)
            str += sc.nextLine() + " ";
        
        String[] list = str.split(" ");
        
        for(int i=0;i<list.length;i++)
            s.add(Integer.parseInt(list[i]));
            
        Collections.sort(s);
        
        int a=0,b=0;
        for(int i=0;i<s.size()-1;i++)
        {
            if(s.get(i)+2==s.get(i+1))  //断号
                a=s.get(i)+1;
            if(s.get(i)==s.get(i+1))    //重号
                b=s.get(i);
        }
        System.out.println(a+" "+b);
    }
}
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

但是在官网没能通过第一个测试点，经过漫长地 $Debug$ ，发现原来是测试一每行输入行尾都有一个空格，而测试点二没有。这个代码还没有改正，只是发现了问题。我又在其他网站进行了测试，发现对于下面这个样例也是 $WA$

30
166 153 266 135 318 258
225 117 282 274 139 288 309 302 238 236
286 269 126 151 278 249
124 283 272 335 212 219 313 221 156 232 155 131 106 157 209
138 180 301 152 133 245
331 118 186 125 299 322 129 281 287 261 243 198 341
239 229
230 224 294 326 194
174 280 140 297 114 233 184 327 146
161 201 328 121 120
200 265 257 192 170 333
242 217 168 164
241 231 320 298 190 213
110 340 312 150 215 182 310
159 296 300 142 227 336 295
267 315 145 270 259 317 165 319 137 202 116 188 264 176
123 334 177 234 314 172 128 175 111 144 256 179
338
260 218 275 173 210 305 113 332 204 149 268 246 167 205 220
325 252 289 250 187 244 306 339 247 290 132 185
183 189 154 308 136 277 191 162 235 273
271 203 193 208 293 158 323 228
134 169 279 222 127 115
291 285 276 329 262 171 163
316 226 181 255 207 184 292 141 105 214
119 148 303 284 337
324 251 321 195
147 311 122 206 196 199 109 307 253 304
211 237 223 178 240 143 107 197 160 330 254 263 112
108 216 130
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

这个代码输出的是

248 0
1

而正确答案是

248 184
1

经过测试，这个代码得到的数组是没有问题的，问题出在第 $26$ 行，将其改成

if(s.get(i)-s.get(i+1)==0)
1

后得到的结果正确，我暂时还没有查到原因。