2021CCPC重赛 1005 Monopoly

hdu链接

Solution

注意对负数的取模方法，注意特判0

查找最后一个小于等于x的方法：
使用 pair <元素值乘 -1 ，数组内下标>，排序后查找第一个大于等于 -x 的值

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<math.h>
#include<queue>
#include<set>
//#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef double dd;
typedef long long ll;
const int MAXN = 100010;
const int MAXM = 400010;
const dd eps = 1e-6;

int n, m;
ll a[MAXN], sum[MAXN];
map<ll, vector<pair<ll, int>>> mp;

void solve(int flag)
{
    for (int i = 1; i <= n;i++)
    {
        ll id = (sum[i] % sum[n] + sum[n]) % sum[n];
        mp[id].push_back({-sum[i], i});
    }
    for (auto now = mp.begin(); now != mp.end();now++)
    {
        sort(now->second.begin(), now->second.end());
    }
    while (m--)
    {
        ll x;
        scanf("%lld", &x);
        if(x == 0)
        {
            printf("0\n");
            continue;
        }
        x *= flag;
        ll xx = (x % sum[n] + sum[n]) % sum[n];
        if (mp.count(xx) == 0)
        {
            printf("-1\n");
            continue;
        }
        pair<ll, int> p = {-x, 0};
        int id = lower_bound(mp[xx].begin(), mp[xx].end(), p) - mp[xx].begin();
        if (id == (int)mp[xx].size())
            printf("-1\n");
        else
        {
            ll ans = (x + mp[xx][id].first) / sum[n] * n + (ll)mp[xx][id].second;
            printf("%lld\n", ans);
        }
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        memset(sum, 0, sizeof(sum));
        mp.clear();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i];
        if(sum[n] > 0)
        {
            solve(1);
        }
        else if(sum[n] < 0)
        {
            for (int i = 1; i <= n;i++)
                sum[i] = -sum[i];
            solve(-1);
        }
        else if(sum[n] == 0)
        {
            map<ll, int> mpp;
            for (int i = 1; i <= n;i++)
            {
                ll id = sum[i];
                if(mpp.count(id) == 0)
                    mpp[id] = i;
            }
            while(m--)
            {
                ll x;
                scanf("%lld", &x);
                if(x == 0)
                {
                    printf("0\n");
                    continue;
                }
                if(mpp.count(x) == 1)
                    printf("%d\n", mpp[x]);
                else
                    printf("-1\n");
            }
        }
    }
}