Codeforces Round #679 (Div. 2, based on Technocup 2021 Elimination Round 1)

C. Perform Easily || 尺取法(滑动窗口)

注意六倍问题

 

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 +9;
const int INF = 1e9 + 7;

int a[7], b[maxn], id[maxn];

struct note
{
    int diff, pos;
}p[maxn*6];

bool cmp(note x, note y)
{
    return x.diff < y.diff;
}

int main()
{
    int n;
    for(int i = 1; i <= 6; ++i)
        scanf("%d", &a[i]);
    scanf("%d", &n);
    int tmp = 1;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &b[i]);
        for(int j = 1; j <= 6; ++j)
        {
            p[tmp].diff = b[i] - a[j];
            p[tmp].pos = i;
            ++tmp;
        }
    }
    sort(p + 1, p + 1 + n * 6, cmp);
    if(n == 1)
    {
        printf("0\n");
        return 0;
    }
    //for(int i = 1; i <= n * 6; ++i) printf("%d %d\n", p[i].diff, p[i].pos);

    int ans = INF, cnt = 0, l = 1;
    for(int r = 1; r <= n * 6; ++r)
    {
        if(!id[p[r].pos]) ++cnt;
        ++id[p[r].pos];
        while(cnt == n)
        {
            ans = min(ans, p[r].diff - p[l].diff);
            id[p[l].pos]--;
            if(!id[p[l].pos]) --cnt;
            ++l;
        }
    }
    printf("%d\n", ans);
    return 0;
}

 

上一篇:note-未完成


下一篇:Nginx-note