CS Academy Round41 Cinema Seats

阅读量：4973 次

发布时间：2019-06-12

本文共 2301 字，大约阅读时间需要 7 分钟。

题目链接：

题目大意：给你一串长度为n的01字符串表示n个座位，0表示有人，1表示没人，移动一个人表示将1换到另一个为0的地方。问在只允许移动一个人或0个人情况下连续座位的最大长度。

解题思路：考虑00100101的前缀和00111223，假设移动了第三个1，那么前缀和变为00000234，即是说我们只要找到前缀和为aaa(a+1)(a+1)(a+1)的最大长度即可。那么就可以枚举然后二分来做了。

需要注意的是当空位的个数比找到的长度小的时候要将结果-1，实际上是这个1被移动到了找到的长度的最末尾。

代码：

1 const int maxn = 1e5 + 5; 2 char str[maxn]; 3 int a[maxn]; 4  5 int main(){ 6     scanf("%s", str); 7     int len = strlen(str), zeronum = 0; 8     a[0] = (str[0] == '0'? 0: 1); 9     zeronum += (str[0] == '0'? 1: 0);10     for(int i = 1; i < len; i++){11         a[i] = a[i - 1] + (str[i] == '0'? 0: 1);12         zeronum += (str[i] == '0'? 1: 0);13     }14     int maxv = 0, maxlen = 0, m = a[len - 1];15     16     for(int i = a[0]; i <= m; i++){17         int tmlen = lower_bound(a, a + len, i + 2) - lower_bound(a, a + len, i);18         if(tmlen > maxlen){19             maxlen = tmlen;20             maxv = i;21         }22     }23     if(maxv != 0) maxlen--;24     if(zeronum < maxlen) maxlen--;25     printf("%d\n", maxlen); 26 }

题目：

Cinema Seats

Time limit: 1000 ms

Memory limit: 128 MB

In a cinema there is a long row of

A group of friends are going to come the cinema. What is the largest size of the group such that they can take a contiguous sequence of seats?

Standard input

The first line contains a binary string of length $i^{th}ith character is 0 is the i^{th}ith seat is empty, and 1 if the seat is taken.$

Standard output

Print the answer on the first line.

Constraints and notes

$\leq N \leq 10^52≤N≤105$

There will be at least one taken seat

There will be at least one free seat

Input	Output	Explanation
10010101	4	You can move the person seating in the `12222111` - the group's chairs were marked with `2`
001100	3	One way is to move the person from the This way, the cinema row becomes `000110`, leaving a sequence of
01000100	6	Move the person from the This way, it's posible to sear a group of size

转载于:https://www.cnblogs.com/bolderic/p/7337976.html

你可能感兴趣的文章