• 欢迎光临~

Gambling

开发技术 开发技术 2022-08-05 次浏览

传送门

题意:
在每一轮游戏玩家选择一个数字从1 ~ 1e9, 在这之后一个甩子有1e9个面旋转,会出现任意的一个数字,如果这个玩家猜对了,他们的钱就会成倍,如果猜错了,他们的钱就会减半,M能够遇见未来,知道n个回合甩子将会展现的数字(x_1, x_2, x_3, cdots, x_n), 他将会选择三个数字a, l, r(l <= r), 他将会完r - l + 1个回合,在这些回合中他将会选择相同的数字,刚开始他有1美元, M想要知道a, l, r使得最后的钱能够最多


思路:
首先区间两端肯定是相同的,题目就是求一段区间众数 - 其他数的最大值,首先数据范围很大,所以先离散化一下,离散化之后,对于每一个数如果知道他左边的最优位置,那就是可以在(O(n))时间内求得答案的,要求这个最优的左端点

可以这样想

  • 之前没出现过这个数,那 (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;
}


程序员灯塔
转载请注明原文链接:Gambling
喜欢 (0)