XJTUOJ 首页 题库 比赛 评测 排名 讨论 帮助
登录 注册
编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#116931 #1474. [L2-4] 数列 Accepted 100 675 ms 4532 K C++ / 1.5 K hmw大帅比 2025-04-18 3:41:33
显示原始代码 
#include <iostream>
#include <fstream>
using namespace std;

int n;
long long a[100010], a1[100010], a2[100010];
int b[100010], c[100010], b1[100010], c1[100010];
int f[100010] = { 0 }, g[100010];
int main() {
    // fstream cin;
    // cin.open("C:/Users/Chen/Downloads/test26.in");
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], a1[i] = a[i] - i, a2[i] = a[i] + i;
    int len = 0;
    for (int i = 1; i <= n; i++) {
        if (len == 0 || a1[i] >= a1[f[len]])
            f[++len] = i;
        else {
            int l = 1, r = len;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (a1[f[mid]] <= a1[i])
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            f[l] = i;
        }
        b[i] = len, b1[i] = a[f[len]];
    }
    len = 0;
    for (int i = n; i >= 1; i--) {
        if (len == 0 || a2[i] >= a2[g[len]])
            g[++len] = i;
        else {
            int l = 1, r = len;
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (a2[g[mid]] <= a2[i])
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            g[l] = i;
        }
        c[i] = len, c1[i] = a[g[len]];
    }
    int ans = 1e9;
    for (int i = 1; i < n; i++) ans = min(ans, n - b[i] - c[i + 1] + (b1[i] == c1[i]));
    cout << ans << endl;
    return 0;
}
子任务 #1
Accepted
得分：100
测试点 #1
Accepted
得分：100
用时：3 ms
内存：404 KiB

输入文件（test1.in） 

10
5 5 8 9 11 12 10 17 15 11

答案文件（test1.out） 

2

用户输出 

2

系统信息 

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

输入文件（test2.in） 

15
21 25 18 18 26 16 26 22 15 25 12 14 15 13 18

答案文件（test2.out） 

9

用户输出 

9

系统信息 

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

输入文件（test3.in） 

1990
1738 699 2477 2058 1245 665 1007 960 1544 2212 2109 1983 2440 2446 2104 1117 1821 1593 809 2201
<9889 bytes omitted>

答案文件（test3.out） 

1878

用户输出 

1878

系统信息 

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

输入文件（test4.in） 

1988
1731 2702 1124 2607 964 2566 1897 2691 2349 1428 1952 2353 1415 2805 1996 2114 1631 2652 1145 2
<9939 bytes omitted>

答案文件（test4.out） 

1874

用户输出 

1874

系统信息 

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

输入文件（test5.in） 

1993
2574 1286 723 2520 1333 1698 2232 886 1858 2442 2473 2124 1094 1289 2031 995 1617 745 1782 952 
<9921 bytes omitted>

答案文件（test5.out） 

1875

用户输出 

1875

系统信息 

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

输入文件（test6.in） 

1995
2160 2788 3252 3598 2516 1835 2805 2577 3611 2414 1775 3607 2440 3752 3252 2176 2789 3625 2370 
<9833 bytes omitted>

答案文件（test6.out） 

1884

用户输出 

1884

系统信息 

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

输入文件（test7.in） 

2000
2126 1787 1871 802 1131 1525 1468 326 965 1805 663 781 1139 833929836 2047 1125 1116 1384 411 1
<9826 bytes omitted>

答案文件（test7.out） 

1882

用户输出 

1882

系统信息 

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

输入文件（test8.in） 

1998
3365 3007 2602 3076 1480 2945 1679 1994 3089 1933 1401 2489 1533 2104 2412 3116 2914 1441 2193 
<9955 bytes omitted>

答案文件（test8.out） 

1881

用户输出 

1881

系统信息 

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

输入文件（test9.in） 

1963
1709 442 1585 1226 1587 518 1764 1167 298 2171 531 562 2130 1958 1074 2068 1007 573 294 1658 41
<9670 bytes omitted>

答案文件（test9.out） 

1855

用户输出 

1855

系统信息 

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

输入文件（test10.in） 

1692
1203 2261 1930 1878 1607 1966 1782 1629 2189 1383 2116 2235 1820 1200 1427 2249 928 2298 1468 1
<8417 bytes omitted>

答案文件（test10.out） 

1587

用户输出 

1587

系统信息 

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

输入文件（test11.in） 

99999
167293 115145 170579 151355 96051 137719 97344 125998 125361 138026 101013 151986 114851 12506
<661694 bytes omitted>

答案文件（test11.out） 

99191

用户输出 

99191

系统信息 

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

输入文件（test12.in） 

99998
80897 46816 67664 95905 97471 81232 36626 105313 524551472 71274 82630 88196 77120 36103 10930
<672521 bytes omitted>

答案文件（test12.out） 

99157

用户输出 

99157

系统信息 

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

输入文件（test13.in） 

99997
17698 33623 93636 64444 46426 114877 83446 54369 45555 78458 100731 63506 77768 27311 98907 92
<666246 bytes omitted>

答案文件（test13.out） 

99177

用户输出 

99177

系统信息 

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

输入文件（test14.in） 

99996
536069077 84239 85100 49388 130630 46339 82023 47912 76828 127216 90090 122980 129937 71379 60
<674978 bytes omitted>

答案文件（test14.out） 

99139

用户输出 

99139

系统信息 

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

输入文件（test15.in） 

95995
55415 68140 66698 76004 95631 87160 56975 59365 118732 55179 65000 112946 47560 81693 100575 4
<645259 bytes omitted>

答案文件（test15.out） 

95132

用户输出 

95132

系统信息 

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

输入文件（test16.in） 

50001
31469 56081 35725 67444 53567 41515 54228 62544 55202 784147106 65594 64852 49072 67172 65388 
<301900 bytes omitted>

答案文件（test16.out） 

49385

用户输出 

49385

系统信息 

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

输入文件（test17.in） 

60001
46065 61556 35285 503262729 16242 59952 62269 65573 67843 27531 58630 46443 22776 72328 61587 
<368588 bytes omitted>

答案文件（test17.out） 

59361

用户输出 

59361

系统信息 

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

输入文件（test18.in） 

70001
69379 80286 83543 58544 35068 36071 42462 53669 35951 77751 62203 65475 63385 52726 41581 5478
<444872 bytes omitted>

答案文件（test18.out） 

69266

用户输出 

69266

系统信息 

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

输入文件（test19.in） 

80001
78200 25540 36099 86505 39760 54493 46061 67924 86450 54960 34344 23671 87229 45281 52147 7455
<512650 bytes omitted>

答案文件（test19.out） 

79260

用户输出 

79260

系统信息 

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

输入文件（test20.in） 

90001
56007 98473 35406 80754 18067 66970 57228 85639 88622 23905 92037 97735 31971 29510 73250 3047
<587485 bytes omitted>

答案文件（test20.out） 

89215

用户输出 

89215

系统信息 

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

输入文件（test21.in） 

100000
102921 87781 38849 39618 66032 88710 113683 104453 34367 78881 50738 82880 103061 82656 12890
<674495 bytes omitted>

答案文件（test21.out） 

99129

用户输出 

99129

系统信息 

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

输入文件（test22.in） 

100000
131754 141439 114491 99504 57992 104470 98407 95471 104360 116967 124964 48857 100947 137949 
<678278 bytes omitted>

答案文件（test22.out） 

99124

用户输出 

99124

系统信息 

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

输入文件（test23.in） 

100000
103200 89882 106975 106378 66516 58320 48946 55704 77493 26690 26760 50501 30545 62179 31955 
<672359 bytes omitted>

答案文件（test23.out） 

99153

用户输出 

99153

系统信息 

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

输入文件（test24.in） 

100000
131102 131024 125414 61134 67464 91162 95011 66129 107749 143626 56062 131968 95373 125137 82
<677915 bytes omitted>

答案文件（test24.out） 

99128

用户输出 

99128

系统信息 

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

输入文件（test25.in） 

100000
38854 41727 58732 54420 82801 41621 58982 83388 79092 33713 100709 13806 32655 86182 15430 31
<657507 bytes omitted>

答案文件（test25.out） 

99200

用户输出 

99200

系统信息 

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

输入文件（test26.in） 

99824
1 14 514 1919 810 998 244353 998244353 7433 8333 9233 10133 11033 11933 12833 13733 14633 1553
<885956 bytes omitted>

答案文件（test26.out） 

7

用户输出 

7

系统信息 

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