RIDDLE - Bí hiểm

Tác giả: flashmt

Ngôn ngữ: C++

#include <iostream>
#include <algorithm>
using namespace std;

int n,k,re,a[100100],d[100100],mx[100100];

int ok(int maxVal)
{
 long long biggest=0;
 for (int i=1;i<=maxVal;i++)
 {
  if (biggest+1<i) return 0;
  if (d[i])
  {
    biggest+=1LL*i*d[i];
    if (biggest>=k) return 1;
  }
 }
 return 0;
}

int main()
{
 int test;
 cin >> test;
 while (test--)
 {
  re=mx[0]=-1;
  cin >> n >> k;
  for (int i=1;i<=n;i++) scanf("%d",&a[i]), mx[i]=max(mx[i-1],a[i]);
  int l=1,r=n,m,last=0;
  while (l<=r)
  {
   m=(l+r)/2;
   if (m<last) 
    for (int i=m+1;i<=last;i++) d[a[i]]--;
   else
    for (int i=last+1;i<=m;i++) d[a[i]]++;
   if (ok(mx[m])) re=m, r=m-1;
   else l=m+1;
   last=m;
  }
  cout << re << endl; 
  for (int i=1;i<=m;i++) d[a[i]]--;
 }
}

Download