第一行包括两个整数n m 代表01串的长度和操作数。
第二行包括一个长度为n的01串s1…n。
接下来m行 每行两个整数Li,Ri代表对区间[Li,Ri]排序。
输出描述
一个长度为n的01串代表答案。
样例1
输入
10 3
1111100000
2 6
4 7
7 10
输出
1010110001
提示
本题共有10个测试点。对于全部测试点 n≤100000 m≤100000。
对于测试点1 2 n=99991 且对于所有的i>1 有Li>Ri−1。
对于测试点3 4 n=99992 LiLi的取值最多不超过50种。
对于测试点5 6 n=99993 对于所有的i>1 有Li=Li−1或Ri=Ri−1。
对于测试点7 8 9 10 n=100000。
我用了快排思路 但是总是没法在1秒内完成所有的样例。程序如下：（备注：另外也试了不排序 用replace函数 也一样超时）
#include <bits/stdc++.h>
using namespace std;
void sort01string(string &s, int left, int right)
{
while(left<right)//循环前提条件
{
char temp;
while(left<right&&s[left]=='0')//左边遇到1之前 向右移位
left++;
while(left<right&&s[right]=='1')//右边遇到0之前 向左移位
right--;
if(left<right) //交换并计数
{
temp=s[left];
s[left]=s[right];
s[right]=temp;
}
}
}
int main()
{
int n=0,m=0;
cin >> n >> m;
string s;
cin >> s;
int R[m]={},i=0;
while (m--)
{ int L=0;
cin >> L >> R[i];
if(i and R[i]<=R[i-1])continue;//判断本次是否不需要排序
sort01string(s, L-1, R[i]-1);
i++;
};
cout << s << '\n';
}
运行之后超时 题目要求1秒内运行完毕 现在有8个测试点都超时。后来又改成这样 还是超时。
#include <stdio.h>
#include <string.h>
int main()
{
int n, m;
char s[100001];
scanf("%d%d\n%s", &n, &m, s);
for (int i = 0, j, k, l, r; i < m; i++)
{
scanf("%d%d", &l, &r);
for (j = l - 1, k = 0; j < r; j++) k += s[j] - 48;
memset(&s[l - 1], '0', r - l - k + 1);
memset(&s[r - k], '1', k);
}
printf("%s\n", s);
return 0;
}
恳请帮忙指导一下。谢谢。
