【CFを打って、アルゴリズムを学びます——3つ星】CodeForces 645 C Enduring Exodus(二分+貪欲)
【CF概要】
コミットリンク:CF 645 C
問題:
C. Enduring Exodus
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
In an attempt to escape the Mischievous Mess Makers' antics, Farmer John has abandoned his farm and is traveling to the other side of Bovinia. During the journey, he and his k cows have decided to stay at the luxurious Grand Moo-dapest Hotel. The hotel consists of n rooms located in a row, some of which are occupied.
Farmer John wants to book a set of k + 1 currently unoccupied rooms for him and his cows. He wants his cows to stay as safe as possible, so he wishes to minimize the maximum distance from his room to the room of his cow. The distance between rooms i and j is defined as |j - i|. Help Farmer John protect his cows by calculating this minimum possible distance.
Input
The first line of the input contains two integers n and k (1 ≤ k n ≤ 100 000) — the number of rooms in the hotel and the number of cows travelling with Farmer John.
The second line contains a string of length n describing the rooms. The i-th character of the string will be '0' if the i-th room is free, and '1' if the i-th room is occupied. It is guaranteed that at least k + 1 characters of this string are '0', so there exists at least one possible choice of k + 1 rooms for Farmer John and his cows to stay in.
Output
Print the minimum possible distance between Farmer John's room and his farthest cow.
Examples
Input
Output
Input
Output
Input
Output
Note
In the first sample, Farmer John can book room 3 for himself, and rooms 1 and 4 for his cows. The distance to the farthest cow is 2. Note that it is impossible to make this distance 1, as there is no block of three consecutive unoccupied rooms.
In the second sample, Farmer John can book room 1 for himself and room 3 for his single cow. The distance between him and his cow is 2.
In the third sample, Farmer John books all three available rooms, taking the middle room for himself so that both cows are next to him. His distance from the farthest cow is 1.
-------------------------------------------------------------------------------------------------------------------
タイトル:
ある農夫はk頭牛を連れて店に泊まり、このホテルにはn室があることが知られており、一部の部屋にはすでに人が住んでおり、部屋の宿泊状況は01列で、0は空、1はすでに人が住んでいることを示し、残りの部屋には(k+1)頭牛/人を収容するのに十分である.牛の安全を保障するため、人が住んでいる部屋は最も遠い牛の部屋からできるだけ小さく、最小距離を出力してほしい.
考え方:
最も遠くに住んでいる牛に一番近いように、最後にこの牛が住んでいる部屋は連続している(元の宿泊者ではない)に違いないし、人が住んでいる位置は中心点に近いほどいい.まず、宿泊の左区間を列挙し、左端に人が住んでいる場合はその点をスキップし、空いている場合はその点を左端とし、空き部屋数k+1の最左位置を二分する.その後、この区間では、空きの最中心位置(距離の遠い方ができるだけ小さい)を探し始め、区間長のパリティを利用して2つのポインタp 1,p 2の初期位置を設定し、その後、必ず空き位置があり、2つのポインタが同時に移動するため、境界を越えることはない.最後に1つの解が見つかったら、最も遠い距離を計算し、最適値より小さい場合は更新します.
コード:
コミットリンク:CF 645 C
問題:
C. Enduring Exodus
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
In an attempt to escape the Mischievous Mess Makers' antics, Farmer John has abandoned his farm and is traveling to the other side of Bovinia. During the journey, he and his k cows have decided to stay at the luxurious Grand Moo-dapest Hotel. The hotel consists of n rooms located in a row, some of which are occupied.
Farmer John wants to book a set of k + 1 currently unoccupied rooms for him and his cows. He wants his cows to stay as safe as possible, so he wishes to minimize the maximum distance from his room to the room of his cow. The distance between rooms i and j is defined as |j - i|. Help Farmer John protect his cows by calculating this minimum possible distance.
Input
The first line of the input contains two integers n and k (1 ≤ k n ≤ 100 000) — the number of rooms in the hotel and the number of cows travelling with Farmer John.
The second line contains a string of length n describing the rooms. The i-th character of the string will be '0' if the i-th room is free, and '1' if the i-th room is occupied. It is guaranteed that at least k + 1 characters of this string are '0', so there exists at least one possible choice of k + 1 rooms for Farmer John and his cows to stay in.
Output
Print the minimum possible distance between Farmer John's room and his farthest cow.
Examples
Input
7 2
0100100
Output
2
Input
5 1
01010
Output
2
Input
3 2
000
Output
1
Note
In the first sample, Farmer John can book room 3 for himself, and rooms 1 and 4 for his cows. The distance to the farthest cow is 2. Note that it is impossible to make this distance 1, as there is no block of three consecutive unoccupied rooms.
In the second sample, Farmer John can book room 1 for himself and room 3 for his single cow. The distance between him and his cow is 2.
In the third sample, Farmer John books all three available rooms, taking the middle room for himself so that both cows are next to him. His distance from the farthest cow is 1.
-------------------------------------------------------------------------------------------------------------------
タイトル:
ある農夫はk頭牛を連れて店に泊まり、このホテルにはn室があることが知られており、一部の部屋にはすでに人が住んでおり、部屋の宿泊状況は01列で、0は空、1はすでに人が住んでいることを示し、残りの部屋には(k+1)頭牛/人を収容するのに十分である.牛の安全を保障するため、人が住んでいる部屋は最も遠い牛の部屋からできるだけ小さく、最小距離を出力してほしい.
考え方:
最も遠くに住んでいる牛に一番近いように、最後にこの牛が住んでいる部屋は連続している(元の宿泊者ではない)に違いないし、人が住んでいる位置は中心点に近いほどいい.まず、宿泊の左区間を列挙し、左端に人が住んでいる場合はその点をスキップし、空いている場合はその点を左端とし、空き部屋数k+1の最左位置を二分する.その後、この区間では、空きの最中心位置(距離の遠い方ができるだけ小さい)を探し始め、区間長のパリティを利用して2つのポインタp 1,p 2の初期位置を設定し、その後、必ず空き位置があり、2つのポインタが同時に移動するため、境界を越えることはない.最後に1つの解が見つかったら、最も遠い距離を計算し、最適値より小さい場合は更新します.
コード:
#include
#include
#include
#include
using namespace std;
char s[100010];
int room[100010];
int main()
{
int n,k,len,le,ri,border,ans,pos;
//
scanf("%d%d",&n,&k);
scanf("%s",s);
room[0]=0;
for(int i=1;i<=n;i++)
{
//
if(s[i-1]-'0')
room[i]=room[i-1];
else
room[i]=room[i-1]+1;
}
//
ans=10e6;
for(int i=1;i<=n;i++)
{
//
if(room[i]==room[i-1])
continue;
le=i;
ri=n;
border=-1;
//
while(le<=ri)
{
int mid=(le+ri)>>1;
if(room[mid]-room[i-1]>k)
{
border=mid;
ri=mid-1;
}
else
le=mid+1;
}
// k+1
if(border!=-1)
{
int len=(border-i),p1,p2;
// ， p1,p2
if(len%2)
{
p1=(border+i)>>1;
p2=(border+i)/2+1;
}
else
{
p1=p2=(border+i)>>1;
}
//
while(1)
{
if((room[p1]!=room[p1-1]))
{
pos=p1;
break;
}
else if(room[p2]!=room[p2-1])
{
pos=p2;
break;
}
p1--;
p2++;
}
//
ans=min(ans,max(pos-i,border-pos));
}
// ， k+1
else
break;
}
printf("%d
",ans);
return 0;
}