• 欢迎光临~

# Gambling

• 之前没出现过这个数，那 (l[id] = i)
• 之前出现过，(i - l[id] + 1) 是当前选中区间的区间长度，(cnt[id])记录这个区间中有多少个与i位置相等的数，(cnt[id] - (i - l[id] - 1 - cnt[id]))这个就是前面对答案的贡献，如果当前的贡献 (<= 0)说明直接转移到 (l[id] = i) 是最优的，如果挡墙的位置 (> 0), 说明还是可以继续更优的，(l[id]) 的值不变，cnt[id]++，相等的数量++

``````#include <bits/stdc++.h>
#define endl 'n'
#define IOS ios::sync_with_stdio(false);
using namespace std;

typedef long long ll;
const ll MAXN = 2e5 + 10;
ll T, n;
ll a[MAXN], b[MAXN];
ll l[MAXN], cnt[MAXN];

int main()
{
IOS; cin.tie(0), cout.tie(0);
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; ++i)
{
l[i] = 0;
cnt[i] = 0;
}
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
b[i] = a[i];
}

sort(b + 1, b + 1 + n);
ll pos = unique(b + 1, b + 1 + n) - b - 1;

map<ll, ll> mp;
for (int i = 1; i <= pos; ++i)
{
mp[b[i]] = i;
}

ll ans = 1, ansa = a[1], ansl = 1, ansr = 1;
for (int i = 1; i <= n; ++i)
{
ll id = mp[a[i]];
if (cnt[id] == 0)
{
l[id] = i;
cnt[id] = 1;
}
else if (cnt[id] != 0)
{
ll length = i - l[id] + 1;
ll same = cnt[id];
ll temp = same - (length - 1 - same);
if (temp <= 0)
{
l[id] = i;
cnt[id] = 1;
}
else
{
cnt[id]++;
//ans = max(ans, temp + 1);
if (ans < temp + 1)
{
ans = temp + 1;
ansa = a[i];
ansl = l[id];
ansr = i;
}
}
}
}

cout << ansa << " " << ansl << " " << ansr << endl;
}
return 0;
}

``````