XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#63323 #1031. JM的特快列车 Accepted 100 631 ms 748 K C++ 11 / 919 B lyh 2021-07-24 15:15:30
显示原始代码 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
typedef unsigned long long ll;
typedef pair<ll, ll> P;
typedef vector<int> v;

int n, m, k;
int d[MAXN];

bool check(int mindist) {
    int cnt = 0;
    int prv = 0;
    for (int i = 1; i <= n + 1; i++) {
        if (d[i] - d[prv] < mindist)
            cnt++;
        else
            prv = i;
    }
    return (cnt <= m);
}

int binary_search(int left, int right) {
    int res = left;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid)) {
            left = mid + 1;
            res = mid;
        } else
            right = mid - 1;
    }
    return res;
}

int main() {
    cin >> n >> m >> k;

    for (int i = 1; i <= n; i++) cin >> d[i];
    d[0] = 0;
    d[n + 1] = k;
    sort(d + 1, d + 1 + n);
    int res = binary_search(0, k);
    cout << res;
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：6 ms
内存：304 KiB

输入文件（1.in） 

5 2 30
4 1 18 15 24

答案文件（1.out） 

4

用户输出 

4

系统信息 

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

输入文件（2.in） 

5 2 30
1 7 15 18 24

答案文件（2.out） 

6

用户输出 

6

系统信息 

Exited with return code 0
测试点 #3
Accepted
得分：100
用时：3 ms
内存：248 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
内存：248 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
用时：4 ms
内存：372 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
用时：4 ms
内存：248 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
内存：248 KiB

输入文件（7.in） 

1 0 34
16

答案文件（7.out） 

16

用户输出 

16

系统信息 

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

输入文件（8.in） 

2 1 23
6 7

答案文件（8.out） 

7

用户输出 

7

系统信息 

Exited with return code 0
测试点 #9
Accepted
得分：100
用时：3 ms
内存：248 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
内存：256 KiB

输入文件（10.in） 

3 3 43
34 8 16

答案文件（10.out） 

43

用户输出 

43

系统信息 

Exited with return code 0
测试点 #11
Accepted
得分：100
用时：48 ms
内存：628 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
用时：48 ms
内存：616 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
用时：43 ms
内存：628 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
用时：47 ms
内存：620 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
用时：45 ms
内存：628 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
用时：50 ms
内存：628 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
用时：47 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
用时：30 ms
内存：628 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
用时：32 ms
内存：748 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
用时：34 ms
内存：624 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
用时：31 ms
内存：636 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
用时：34 ms
内存：628 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
用时：34 ms
内存：696 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
用时：38 ms
内存：652 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
用时：33 ms
内存：628 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号