[NCPC2021] Antenna Analysis | 思维递推

题目描述

Åke has heard that there may be some suspicious 5G radiation in his city. To test this, he uses the antenna on his roof to measure the 5G level each day. However, he does not know how he should analyze the data.

We are given the measurements for n consecutive days as a list of numbers x1 , . . . , xn (where xi denotes the measurement for day i) and a constant c that measures how much Åke expects the radiation to vary from day to day. We want to find, for each day i, the most significant difference between the measurement on day i and any earlier day, after the expected variations are taken into account. More precisely, the goal is to find the maximum value of |xi − xj | − c·|i − j| where j ≤ i. I.e., we want to find a large difference in 5G level that has happened recently.

输入

The first line of input contains the two integers n and c (1 ≤ n ≤ 4 · 105 , 1 ≤ c ≤ 106 ), the number of measurements and expected day-to-day variation. The second input line contains the n integers x1 , x2 , . . . , xn (1 ≤ xi ≤ 106 for i = 1, 2, . . . , n), giving the measurements of the n days.

输出

Output n integers y1 , . . . , yn , where yi is the most significant difference on day i.

样例输入 Copy

5 1
2 7 1 5 4

样例输出 Copy

0 4 5 3 1

题意：

对每一个位置，输出：

∣ x_i − x_j ∣ − c⋅∣i − j∣ ,  j ≤ i

只需要维护最大值最小值即可

int a[maxn];
int main() {
  ll n = read,c = read;
  ll mini = 0, maxx = 0;
  ll x = read;
  maxx = -x;
  mini = x;
  a[1] = 0;
  for(int i=2; i<=n; i++) {
    ll x = read;
    maxx -= c,mini -= c;
    a[i] = max(mini-x,max(0LL,maxx+x));
    maxx = max(maxx,-1 * x);
    mini = max(mini, x);
  }
  for(int i=1; i<=n; i++) {
    printf("%d ",a[i]);
  }
  return 0;
}

队友代码：

const int maxn=4e5+7;
ll n,c,a[maxn],b[maxn],mx,mi;
int main(){
  n=read(); c=read();
  for(int i=0;i<n;i++)  a[i]=read();
  mx=-a[0];
  mi=a[0];
  for(int i=1;i<n;i++){
    mx-=c;  mi-=c;
    mx=max(mx,-a[i-1]-c);
    mi=max(mi,a[i-1]-c);
    b[i]=max(a[i]+mx,-a[i]+mi);
    if(b[i]<0)  b[i]=0;
  }
  for(int i=0;i<n;i++)  cout<<b[i]<<' ';
}