[USACO17FEB]Why Did the Cow Cross the Road II S

题目描述

The long road through Farmer John's farm has $N$ crosswalks across it, conveniently numbered $1 \ldots N$ ( $1 \leq N \leq 100,000$ ). To allow cows to cross at these crosswalks, FJ installs electric crossing signals, which light up with a green cow icon when it is ok for the cow to cross, and red otherwise. Unfortunately, a large electrical storm has damaged some of his signals. Given a list of the damaged signals, please compute the minimum number of signals that FJ needs to repair in order for there to exist some contiguous block of at least $K$ working signals.

共有N个信号灯，编号为1~N，有B个信号灯损坏，给你它们的编号。

问，最少修好几个信号灯，可以有K个编号连续的信号灯。

输入输出格式

输入格式：

The first line of input contains $N$ , $K$ , and $B$ ( $1 \leq B, K \leq N$ ). The next $B$ lines each describe the ID number of a broken signal

输出格式：

Please compute the minimum number of signals that need to be repaired in order for there to be a contiguous block of $K$ working signals somewhere along the road.

输入输出样例

输入样例#1：

输出样例#1：

1
非常简单的二分。
可知当a[i]-a[j]>=k时，求min(i-j-1);
二分a[i]-k即可
此题卡常数，把能减少时间的方法都用上

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<set>

 using namespace std;

 int ans=2e9,n,a[],k,b,l,sum[];

 int dinary(int x)

 {int as;

     int l=,r=b;

     while (l<=r)

     {

         int mid=(l+r)/;

         if (a[mid]<x) as=mid,l=mid+;

         else r=mid-;

     }

   return as;

 }

 int get()

 {int s=;

 char ch;

     ch=getchar();

     while (ch<''||ch>'') ch=getchar();

     while (ch>=''&&ch<='')

     {

         s=s*+ch-'';

         ch=getchar();

     }

   return s;

 }

 int main()

 {

     cin>>n>>k>>b;

     int last,l,i,j;

     for (i=;i<=b;i++)

     {

         a[i]=get();

     }

     sort(a+,a+b+);

     a[++b]=n+;

     for (i=;i<=b;i++)

     {

         if (a[i]<=k) continue;

         int pos=dinary(a[i]-k);

         ans=min(ans,i-pos-);

     }

 cout<<ans;

 }

巴特西

[USACO17FEB]Why Did the Cow Cross the Road II S

题目描述

输入输出格式

输入输出样例

最新文章

热门文章