XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#25710 #1031. JM的特快列车 Accepted 100 490 ms 728 K C++ 11 / 902 B dytc 2020-06-27 18:50:24
显示原始代码 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>
#define x first
#define y second
typedef long long ll;
using namespace std;
const int N = 1e5 + 100;
int n, m, k;
int a[N];

int check(int mid) {
    int j = 0;
    int cnt = 0;
    for (int i = 1; i <= n + 1; i++)  //这个指针只会遍历一遍
    {
        if (a[i] - a[j] < mid)
            cnt++;
        else
            j = i;
    }
    return cnt <= m;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    a[0] = 0, a[n + 1] = k;
    // for(int i = 0 ;i <= n+1 ;i++) cout<<a[i]<<endl;
    int l = 0, r = k, res;
    while (l <= r) {
        int mid = (l + r) >> 1;
        // 首先这种二分先要去保证这个这个mid值是一定可以取到的,所以上面用的是 <=
        if (check(mid))
            l = mid + 1, res = mid;
        else
            r = mid - 1;
    }
    cout << res << endl;

    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：3 ms
内存：360 KiB

输入文件（1.in） 

5 2 30
4 1 18 15 24

答案文件（1.out） 

4

用户输出 

4

系统信息 

Exited with return code 0
测试点 #2
Accepted
得分：100
用时：2 ms
内存：356 KiB

输入文件（2.in） 

5 2 30
1 7 15 18 24

答案文件（2.out） 

6

用户输出 

6

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：2 ms
内存：360 KiB

输入文件（3.in） 

5 2 25
2 14 11 21 17

答案文件（3.out） 

4

用户输出 

4

系统信息 

Exited with return code 0
测试点 #4
Accepted
得分：100
用时：4 ms
内存：280 KiB

输入文件（4.in） 

10 7 47
46 29 15 28 11 35 1 3 43 41

答案文件（4.out） 

7

用户输出 

7

系统信息 

Exited with return code 0
测试点 #5
Accepted
得分：100
用时：3 ms
内存：240 KiB

输入文件（5.in） 

7 5 48
35 24 28 36 8 40 22

答案文件（5.out） 

13

用户输出 

13

系统信息 

Exited with return code 0
测试点 #6
Accepted
得分：100
用时：3 ms
内存：352 KiB

输入文件（6.in） 

7 1 37
5 18 11 23 14 22 2

答案文件（6.out） 

2

用户输出 

2

系统信息 

Exited with return code 0
测试点 #7
Accepted
得分：100
用时：3 ms
内存：280 KiB

输入文件（7.in） 

1 0 34
16

答案文件（7.out） 

16

用户输出 

16

系统信息 

Exited with return code 0
测试点 #8
Accepted
得分：100
用时：3 ms
内存：268 KiB

输入文件（8.in） 

2 1 23
6 7

答案文件（8.out） 

7

用户输出 

7

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：3 ms
内存：352 KiB

输入文件（9.in） 

7 0 20
15 9 6 4 13 3 14

答案文件（9.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #10
Accepted
得分：100
用时：3 ms
内存：348 KiB

输入文件（10.in） 

3 3 43
34 8 16

答案文件（10.out） 

43

用户输出 

43

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：39 ms
内存：676 KiB

输入文件（11.in） 

95081 77335 568254347
160731933 121592942 545359032 42372661 94548234 31387055 297203963 120233938 
<930969 bytes omitted>

答案文件（11.out） 

25967

用户输出 

25967

系统信息 

Exited with return code 0
测试点 #12
Accepted
得分：100
用时：38 ms
内存：704 KiB

输入文件（12.in） 

93202 26371 640243133
544564116 20205828 399307350 600697625 98046473 248585032 150738566 19380659 
<915056 bytes omitted>

答案文件（12.out） 

2706

用户输出 

2706

系统信息 

Exited with return code 0
测试点 #13
Accepted
得分：100
用时：32 ms
内存：700 KiB

输入文件（13.in） 

98726 15172 4863256
4061736 2523417 2966284 1702310 1537399 4510660 4013440 4354876 2840737 4397394
<767088 bytes omitted>

答案文件（13.out） 

9

用户输出 

9

系统信息 

Exited with return code 0
测试点 #14
Accepted
得分：100
用时：34 ms
内存：632 KiB

输入文件（14.in） 

100000 99862 197697696
189350415 146517714 171890535 104293377 143894247 186136108 163590632 166302
<943029 bytes omitted>

答案文件（14.out） 

1420180

用户输出 

1420180

系统信息 

Exited with return code 0
测试点 #15
Accepted
得分：100
用时：34 ms
内存：644 KiB

输入文件（15.in） 

100000 142 25917879
25050015 18738442 17905039 7617439 1530367 10773344 8382003 14486136 11569183 2
<856866 bytes omitted>

答案文件（15.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #16
Accepted
得分：100
用时：38 ms
内存：704 KiB

输入文件（16.in） 

100000 0 409108430
185938952 21819912 310245988 320735736 37814393 158165858 368886326 407468247 43
<971434 bytes omitted>

答案文件（16.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #17
Accepted
得分：100
用时：37 ms
内存：656 KiB

输入文件（17.in） 

100000 100000 595536117
374138900 81845477 282044690 198472228 155427374 591666576 348669485 576466
<979298 bytes omitted>

答案文件（17.out） 

595536117

用户输出 

595536117

系统信息 

Exited with return code 0
测试点 #18
Accepted
得分：100
用时：22 ms
内存：664 KiB

输入文件（18.in） 

100000 69297 100001
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 3
<588817 bytes omitted>

答案文件（18.out） 

3

用户输出 

3

系统信息 

Exited with return code 0
测试点 #19
Accepted
得分：100
用时：25 ms
内存：704 KiB

输入文件（19.in） 

100000 85178 1000000000
2 4 6 8 9 10 12 14 16 18 19 20 22 23 24 25 27 29 31 32 33 35 36 37 39 41 42
<625941 bytes omitted>

答案文件（19.out） 

9

用户输出 

9

系统信息 

Exited with return code 0
测试点 #20
Accepted
得分：100
用时：28 ms
内存：704 KiB

输入文件（20.in） 

100000 14352 1000000000
1 2 3 5 7 8 10 12 13 15 16 18 20 21 23 25 26 27 29 31 32 33 35 37 38 40 41 
<625955 bytes omitted>

答案文件（20.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #21
Accepted
得分：100
用时：24 ms
内存：720 KiB

输入文件（21.in） 

100000 99999 100031
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 3
<588817 bytes omitted>

答案文件（21.out） 

50015

用户输出 

50015

系统信息 

Exited with return code 0
测试点 #22
Accepted
得分：100
用时：26 ms
内存：728 KiB

输入文件（22.in） 

100000 45195 916842072
4 5 9 11 12 13 14 17 21 25 27 30 34 36 40 42 45 46 49 50 54 57 61 62 64 65 6
<655452 bytes omitted>

答案文件（22.out） 

3

用户输出 

3

系统信息 

Exited with return code 0
测试点 #23
Accepted
得分：100
用时：32 ms
内存：728 KiB

输入文件（23.in） 

100000 2321 623818276
4 7 11 14 16 20 24 28 29 31 33 37 41 44 47 51 52 55 59 63 65 67 68 70 74 76 7
<655432 bytes omitted>

答案文件（23.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
测试点 #24
Accepted
得分：100
用时：27 ms
内存：704 KiB

输入文件（24.in） 

100000 63443 223616492
2 4 6 9 10 14 16 20 23 25 28 29 33 36 38 40 41 42 44 45 49 51 54 58 59 61 64
<655623 bytes omitted>

答案文件（24.out） 

5

用户输出 

5

系统信息 

Exited with return code 0
测试点 #25
Accepted
得分：100
用时：25 ms
内存：608 KiB

输入文件（25.in） 

100000 10406 352363072
1 2 3 4 5 6 10 14 16 18 19 23 25 27 30 34 38 39 43 47 48 51 52 54 55 58 60 6
<655475 bytes omitted>

答案文件（25.out） 

1

用户输出 

1

系统信息 

Exited with return code 0
XJTUOJ Powered by SYZOJ. | 鲁ICP备2020034929号