E - Elevator ——前缀和+树状数组

发布时间:2024年01月20日

在编号为 1 到 m 的 m 层建筑中,有 n 部电梯参加从 0 开始的速度竞赛。
第 i 部电梯将在1层 用 xi 秒启动,并以每秒1层的速度上升。
此外,除 1 层和 m 层外,每层楼都有一个按钮,如果按下按钮,到达该层的第一部电梯将停止 1 秒。如果多部电梯同时到达一个楼层,则只有指数最小的电梯才会被视为第一部。
现在没有按钮,但你可以在比赛开始前按下某些楼层的按钮。请注意,比赛开始后不能按下按钮。
现在你想知道你是否能够通过按下按钮来操纵比赛,使第 i 部电梯第一个到达 m 层,如果可以的话,你至少要按下多少按钮。如果同时有多部电梯到达 m 层,则只有编号最小的电梯才会被视为第一部。

输入
第一行包含两个正整数n,m(1 ≤ n ≤ 5e5,2 ≤ m ≤ 1e9),表示电梯和楼层的数量。
第二行包含n个正整数x1,…,xn(1 ≤ xi ≤ 1e9),表示电梯的启动时间。

输出
输出 n 行。第 i 行应该包含使第 i 部电梯第一个到达m层所需按下的最小按钮数。如果不可能,则输出?1。

Input
6 20
3 8 12 6 9 9
Output
0
8
-1
4
13
14


解析:
要想要第 i 部电梯第一,就得通过按按钮的操作,让其它比该电梯早到达的电梯的到达时间延后;
在早到达的电梯中,编号id ≤ i的电梯的到达时刻应该是 xi+1,因为如果同时有多部电梯到达 m 层,则只有编号最小的电梯才会被视为第一部 (中间上升的时间相同,省略);
在早到达的电梯中,编号id > i的电梯的到达时刻应该是 xi。

所以用树状数组维护编号id的个数,记录比 i 小的电梯个数。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=2e6+10;
int n,m;
int tr[N];
struct node
{
    int x,id;
}str[N];
bool cmp(node a,node b)
{
    if (a.x==b.x) return a.id<b.id;
    else return a.x<b.x;
}
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int c)
{
    for (int i=x;i<=n;i +=lowbit(i)) tr[i] +=c;
}
int query(int x)
{
    int ans=0;
    for (int i=x;i>0;i -=lowbit(i)) ans +=tr[i];
    return ans;
}
int s[N];
map <int,int> k;
void solve()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        cin>>str[i].x;
        str[i].id=i;
    }
    sort (str+1,str+n+1,cmp);
    for (int i=1;i<=n;i++) s[i]=s[i-1]+str[i].x;
    for (int i=1;i<=n;i++)
    {
        int cnt=i-1;
        int id=str[i].id;
        int num=query(id-1);                                    //num*(str[i].x+1) 表示 id ≤ i 时,这些电梯到达时间应是str[i].x+1
        int ans=num*(str[i].x+1)+(cnt-num)*str[i].x-s[i-1];     //(cnt-num)*str[i].x 表示 id > i 时,这些电梯到达时间应是str[i].x
        if (ans>m-2) ans=-1;                                    //实际上这些电梯的到达时间为s[i-1]
        k.insert({id,ans});                                     //所以答案是num*(str[i].x+1)+(cnt-num)*str[i].x-s[i-1]
        add(id,1);
    }
    for (auto [x,y]:k) cout<<y<<endl;
}
signed main()
{
    ios;
    int T=1;
    //cin>>T;
    while (T--) solve();
    return 0;
}

文章来源:https://blog.csdn.net/m0_74403543/article/details/135710706
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。