计蒜客:重铸项链

计蒜客:重铸项链_第1张图片

思路:

乍一看好像没法做的样子,仔细一想。 1e5的数据,肯定是nlogn的做法;
所以不难想到二分答案,然后check。

AC代码

#include 
using namespace std;

int a[100010], n, m;

bool check(int k)
{
    for(int i = 0; i + k - 1 < n; i++)
    {
        vector<bool> vis(m + 1, 0);
        for(int j = 0; j < k; j++)
    	{
       		vis[a[i + j]] = 1;
    	}
        int flag = 1;
    	for(int i = 1; i <= m; i++)
    	{
        	if(!vis[i])
        	{
            	flag = 0;
            	break;
        	}
    	}
    	if(flag)
       		return true;
    }
    return false;
}

int main()
{
    
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    int l = m, r = n;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check(mid))
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    printf("%d\n", l);
    return 0;
}

你可能感兴趣的