【习题 8-17 UVA - 11536】Smallest Sub-Array

在这里输入题意

【题解】

尺取法。
考虑一个1..i的窗口。
里面在到达了i位置的时候恰好有1..k这些数字了。
为了更接近答案。
显然可以试着让左端点变成2.(如果还能有1..k这些数字的话。
所以有1..k这些数字之后。就让左端点尽可能往右。

然后尝试更新答案。

然后让右端点右移。

重复上述过程。

【代码】

#include <bits/stdc++.h>

#define ll long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define all(x) x.begin(),x.end()

#define pb push_back

#define ls l,mid,rt<<1

#define rs mid+1,r,rt<<1

using namespace std;

const double pi = acos(-1);

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

const int M = 1e3;

const int N = 1e6;

int n,m,k,a[N+10];

int cnt[M+10];

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    int T;

    cin>> T;

    int kase = 0;

    while (T--){

        memset(cnt,0,sizeof cnt);

        cin >> n >> m >> k;

        for (int i = 1;i <= 3;i++) a[i] = i;

        for (int i= 4;i<= n;i++) a[i] = (a[i-1]+a[i-2]+a[i-3])%m + 1;

        int rest = k,l = 1,ans = n+10;

        for (int i = 1;i <= n;i++){

            if (a[i]>k) continue;

            cnt[a[i]]++;

            if (cnt[a[i]]==1) rest--;

            if (rest==0){

                while (a[l]>k || cnt[a[l]]>1){

                    if (a[l]>k){

                        l++;

                        continue;

                    }

                    cnt[a[l]]--;

                    l++;

                }

                ans = min(ans,i-l+1);

            }

        }

        cout<<"Case "<<++kase<<": ";

        if (ans>n){

            cout<<"sequence nai"<<endl;

        }else{

            cout<<ans<<endl;

        }

    }

	return 0;

}

巴特西

【习题 8-17 UVA - 11536】Smallest Sub-Array

最新文章

热门文章