射箭(arrow)

Description?

FJ很喜歡看射箭比賽，看著運(yùn)動(dòng)員們一個(gè)個(gè)精湛的技藝，令他頭暈?zāi)垦Ｄぐ莶灰选６宜矚g給那些射箭選手打分，他想如果一位選手能在盡量短的時(shí)間段內(nèi)射出所有可能的環(huán)數(shù)，那么他的得分就是那段最短時(shí)間的長(zhǎng)度。
現(xiàn)在，FJ告訴你其中一位選手共射出了n支箭，當(dāng)然他每個(gè)單位時(shí)間射出一只箭。FJ還會(huì)告訴你他射出的每支箭的環(huán)數(shù)。而且環(huán)數(shù)總共的可能性有m種，環(huán)數(shù)分別為1-m，請(qǐng)你幫他算過這位選手在他心目中的分?jǐn)?shù)。

Input?

輸入文件共兩行
第一行兩個(gè)數(shù)n，m。
第二行一共n個(gè)數(shù)表示那位選手每一箭的環(huán)數(shù)。

Output

輸出文件只有一個(gè)數(shù)，表示這位選手的得分。如果這位運(yùn)動(dòng)員無法在這n箭中射出所有的環(huán)數(shù)，則輸出-1。

Sample Input?

12 5

2 5 3 1 3 2 4 1 1 5 4 3

Sample Output?

6

說明：這位選手從第2支箭到第7支箭射出了所有可能的環(huán)數(shù)，因此他的得分是6。

Hint

30% n<=1000 m<=20。
100% n<=1000000 m<=2000。?

算法：

根據(jù)下標(biāo)計(jì)數(shù)統(tǒng)計(jì)環(huán)的個(gè)數(shù)進(jìn)行添加右邊的環(huán)或者刪除左邊的環(huán)。

步驟：

1 以環(huán)數(shù)作為下標(biāo)從右邊進(jìn)行添加環(huán)的操作，當(dāng)值為1的時(shí)候，表示產(chǎn)生新的環(huán)，則進(jìn)行h的累加；

2 h==m，可以進(jìn)行比較存儲(chǔ)；

3 h==m，可以從左邊進(jìn)行刪除環(huán)的操作；當(dāng)環(huán)為下標(biāo)的值為0時(shí)，表示失去一個(gè)環(huán)，就停止刪除，中斷，再繼續(xù)從右邊進(jìn)行增加環(huán)的操作；

#include<bits/stdc++.h> using namespace std; long long n,m,ans=INT_MAX,sum,l,r,p,k,c[20000001],s[1000009],x; int main() {cin>>n>>m;for(int i=1;i<=n;i++)cin>>s[i];for(int i=1;i<=n;i++){r=i;x=s[i];c[x]++;if(c[x]==1) k++;if(k==m){p=1;for(;;){sum=r-l+1;if(sum<ans) ans=sum;x=s[l];c[x]--;l++;if(c[x]==0){k--;break;}}}}if(p==0) ans=0;cout<<ans;return 0; }

總結(jié)

以上是生活随笔為你收集整理的射箭(arrow)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。