2019ACM-ICPC徐州网络赛-E-XKC's basketball team（set+贪心）

电玩女神 2023-06-05 12:33 4阅读 0赞

**E-XKC's basketball team**

XKC , the captain of the basketball team , is directing a train of nn team members. He makes all members stand in a row , and numbers them 1 \\cdots n1⋯n from left to right.

The ability of the ii-th person is w\_iwi , and if there is a guy whose ability is not less than w\_i+mwi\+mstands on his right , he will become angry. It means that the jj-th person will make the ii-th person angry if j>ij>i and w\_j \\ge w\_i+mwj≥wi\+m.

We define the anger of the ii-th person as the number of people between him and the person , who makes him angry and the distance from him is the longest in those people. If there is no one who makes him angry , his anger is \-1−1 .

Please calculate the anger of every team member .

### Input ###

The first line contains two integers nn and m(2\\leq n\\leq 5\*10^5, 0\\leq m \\leq 10^9)m(2≤n≤5∗105,0≤m≤109) .

The following line contain nn integers w\_1..w\_n(0\\leq w\_i \\leq 10^9)w1..wn(0≤wi≤109) .

### Output ###

A row of nn integers separated by spaces , representing the anger of every member .

#### 样例输入复制 ####

6 1
    3 4 5 6 2 10

#### 样例输出复制 ####

4 3 2 1 0 -1
    
    思路
    
    标程用的是单调队列+二分，我用的是set+map，想法差不多。从后往前遍历arr[],严格单调递增插入arr[i],并用map将arr[i]的下标存起来,
    ans[i]=lower_bound(arr[i]+m)==set.end()?-1:lower_bound(arr[i]+m)

1 #include <bits/stdc++.h>
     2 #pragma GCC optimize(3)
     3 using namespace std;
     4 typedef long long ll;
     5 const int maxn=1e6+7;
     6 set<int> ste;
     7 typedef set<int>::iterator sii;
     8 map<int,int> MAP;
     9 int ans[maxn];
    10 int arr[maxn];
    11 int main()
    12 {
    13     int n,m;
    14     scanf("%d%d",&n,&m);
    15     for(int i=1;i<=n;++i)
    16     {
    17         scanf("%d",&arr[i]);
    18     }
    19     for(int i=n;i>0;--i)
    20     {
    21         sii it=ste.lower_bound(arr[i]+m);
    22         if(it!=ste.end())
    23         ans[i]=MAP[*it]-i-1;
    24         else ans[i]=-1;
    25         if(ste.empty())
    26         {
    27             ste.insert(arr[i]);
    28             MAP[arr[i]]=i;
    29         }
    30         else
    31         {
    32             it=--ste.end();
    33             if(arr[i]>(*it))
    34             {
    35                 ste.insert(arr[i]);
    36                 MAP[arr[i]]=i;
    37             }
    38         }
    39     }
    40     for(int i=1;i<=n;++i)
    41     {
    42         printf("%d",ans[i]);
    43         if(i<n)printf(" ");
    44         else printf("\n");
    45     }
    46     return 0;
    47 }
    48 /*
    49 5 2
    50 5 4 3 2 1
    51 */

转载于:https://www.cnblogs.com/CharlieWade/p/11482359.html