UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#190879#3392. 排序算法gaojieming100219ms5984kbC++11813b2023-10-07 18:47:512023-10-07 21:37:23

answer

#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pn putchar('\n')
#define maxint 2147483647
#define min(x,y) (x<y?x:y)
#define max(x,y) (x>y?x:y)
#define maxn 1000005
using namespace std;
int n,las;
int f[maxn];
string s;
il bool check()
{
    for(int i=1;i<n;i++)
        if(s[i]=='1'&&s[i+1]=='0')
            return 0;
    return 1;
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    cin>>s;
    n=s.size();
    s=' '+s;
    if(check())
        return puts("0"),0;
    for(int i=n;i;i--)
    {
        if(s[i]=='0')continue;
        if(n==i)f[i]=0;
        else
            f[i]=n-i+!(i&1);
        if(f[i]<f[las])
            f[i]=f[las]+1;
        las=i,n--;
    }
    printf("%d",f[las]);
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1272kb

input:

0111101100111110101010111111000001111011101001100010101011011110110111010001000100100010000000110011...

output:

2561

result:

ok single line: '2561'

Test #2:

score: 10
Accepted
time: 0ms
memory: 1268kb

input:

0111110100010001011100000100000110010100010010100111001000111000101101001101010110001001010111010111...

output:

2566

result:

ok single line: '2566'

Test #3:

score: 10
Accepted
time: 0ms
memory: 1272kb

input:

0000100110010010011000111011110100010000111110000011001111010010000111100110011110000001010100100110...

output:

2532

result:

ok single line: '2532'

Test #4:

score: 10
Accepted
time: 30ms
memory: 3124kb

input:

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

978092

result:

ok single line: '978092'

Test #5:

score: 10
Accepted
time: 28ms
memory: 3124kb

input:

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

893086

result:

ok single line: '893086'

Test #6:

score: 10
Accepted
time: 24ms
memory: 3128kb

input:

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

971188

result:

ok single line: '971188'

Test #7:

score: 10
Accepted
time: 32ms
memory: 5984kb

input:

0111111010011110001111001111001111001101011000000100101001001001010111011011111101110011001110001011...

output:

500148

result:

ok single line: '500148'

Test #8:

score: 10
Accepted
time: 36ms
memory: 5984kb

input:

0000000000011001101010010110101100001000100110000110001010110111001101100001100001011010011001110111...

output:

500128

result:

ok single line: '500128'

Test #9:

score: 10
Accepted
time: 36ms
memory: 5984kb

input:

0000011000110110100100101101101110101110001101100010101101010001100111001111111011010010101000010011...

output:

500223

result:

ok single line: '500223'

Test #10:

score: 10
Accepted
time: 33ms
memory: 5984kb

input:

1100010011000000001011011110010100111101010001101000100110011111110111000110111110000101000010001001...

output:

500212

result:

ok single line: '500212'

Extra Test:

score: 0
Extra Test Passed