NOJ 102かっこいい神妹紙の誕生日プレゼント(ダブルポインタ)

イケメンの誕生日プレゼント
時間制限(通常/Java):
1000 MS/3000 MS運転メモリ制限:65536 KByte
総提出:427試験合格:41
試合の説明
A協大牛帅神の妹紙は最近また誕生日を過ぎて、しかし妹紙の心の中はとっくに1つの欲しい贈り物があって、妹紙の欲しい贈り物は10種類の珍しいダイヤモンドで、かっこいい神は妹紙の要求を満たすために、あちこち探してダイヤモンドが1つの神秘的な場所にあることを知っていて、この場所は多くの神があって、すべての神霊は1列に立って、すべての神の手の上で1種のダイヤモンドがあって、しかし、怠け者のハンサムな神は歩くことを少なくするために、できるだけ隣接する神を訪問することを少なくしたいと思って、彼らの手からダイヤモンドを獲得して、妹の紙が1種のダイヤモンドに対して需要の数のいくらを知っていて、ハンサムな神に最低でどれだけ連続する神を訪問してやっと妹の紙を獲得してダイヤモンドを必要とすることができることを求めます.
入力
本題は複数組のサンプルで、最初の行に整数t(t<=100)を入力し、サンプルの個数を表し、各組のサンプルに対して、
第1の行為は0-9の数字からなる文字列(長さが100000未満)で、立っている神霊を表し、各数字はその神がダイヤモンドを何番持っているかを表しています.
第2行為の10個の数字、それぞれ妹の紙の必要とする0-9番のダイヤモンドがいくらなことを表します
しゅつりょく
各サンプルのセットには、少なくとも複数の連続した神にアクセスして妹紙のニーズを満たすことができることを示す数字が出力され、満足できない場合は「Let's break up」が出力されます.
サンプル入力
2 1234567890 0 0 0 1 1 0 1 0 0 0 1234567890 2 0 0 0 0 0 0 0 0 0
サンプル出力
4 Let's break up
タイトルリンク:クリックしてリンクを開く
両指針法は、出現回数を記録し、尾針を後ろに移動し、頭針をフォローし、動的に数を更新し、最小長を記録する.
ACコード:

#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
#include "cstdlib"
using namespace std;
typedef long long ll;
typedef pair pii;
#define st first
#define nd second
#define exp 1e-8
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 5;
int t, n, need[15], has[15];
char s[MAXN];
bool Judge()
{
    for(int i = 0; i < 10; ++i)
        if(has[i] < need[i]) return false;
    return true;
}
int main(int argc, char const *argv[])
{
    scanf("%d", &t);
    while(t--) {
        memset(has, 0, sizeof(has));
        scanf("%s", s);
        for(int i = 0; i < 10; ++i)
            scanf("%d", &need[i]);
        int st = 0, ed = 0, ans = INF, len = strlen(s);
        while(ed < len) {
            while(!Judge() && ed < len) {
                has[s[ed] - '0']++;
                ed++;
            }
            while(Judge() && st < ed) {
                ans = min(ans, ed - st);
                has[s[st] - '0']--;
                st++;
            }
        }
        if(ans == INF) printf("Let's break up
");
        else printf("%d
", ans);
    }
    return 0;
}