2022.10.22每日一题

饿饿 饭饭

题目描述

有 \(n\) 个同学正在排队打饭，第 \(i\) 个同学排在从前往后第 \(i\) 个位置。但是这天食堂内只有一个食堂阿姨，为了使同学们都能尽快的吃上饭，每一个同学在打完一份饭之后就会排在队伍的末尾先吃着打到的饭，我们知道第 \(i\) 个同学的饭量为 \(a_i\)，也就是说第 \(i\) 个同学要吃 \(a_i\) 份饭才能吃饱，当一位同学吃饱后，他就会立刻离开食堂，不会排在队伍的末尾。食堂阿姨想知道，在打完 \(k\) 份饭之后，队伍的样子是怎样的，但是食堂阿姨数学不太好，想让你帮忙想想办法

输入格式

第一行给出两个整数 \(n\)，\(k\)。
第二行给出 \(n\) 个整数 \(a_1,a_2,......a_n\)。

输出格式

如果食堂阿姨打饭数少于 \(k\)，请输出-1。
否则按照队伍顺序输出每一个同学的编号。

样例输入1

3 3
1 2 1

样例输出1

2

样例输入2

4 10
3 3 2 1

样例输出2

-1

样例输入3

7 10
1 3 3 1 2 3 1

样例输出3

6 2 3

数据规模

数据保证 \(1≤n≤10^5, 0≤k≤10^{14}, 1≤a_i≤10^9\)。

解题思路

首先 \(k\) 很大，选择模拟的话必然会超时。考虑一下，我们在不超过 \(k\) 的情况下能打多少轮饭，这里的话采取二分的方式确定。这样对于剩下的 \(k\)，我们再进行模拟即可

C++代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int, int> PII;
typedef long long LL;

int n;
LL k;
int a[N], c[N];

LL cal(int x) // 前x轮打饭量
{
    LL res = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(a[i] <= x) res += a[i]; // 吃饱了
        else res += x;
    }
    return res;
}

int main()
{
    LL sum = 0;
    scanf("%d%lld", &n, &k);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    if(sum < (LL)k) puts("-1");
    else
    {
        int l = 0, r = 1e9;
        while(l + 1 < r)
        {
            int mid = l + r >> 1;
            if(cal(mid) <= k) l = mid;
            else r = mid;
        }
        k -= cal(l); // 剩余打饭量，剩余的饭肯定不够再来一轮
        int total = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(a[i] > l)
            {
                c[++ total] = i;
            }
        }
        for(int i = k + 1; i <= total; i ++) // 再次打 k 次饭，所以跳过前面 k 个人
            printf("%d ", c[i]);
        for(int i = 1; i <= k; i ++)
            if(a[c[i]] != l + 1)
                printf("%d ", c[i]);
    }
    return 0;
}