动态规划基础题(第4题): 此累积和非累积和

碎碎念

这道题稍有些水，比赛时遇到这种题就开心了。

标签

累积和、排序

合集

动态规划、累积和、排序

题目地址

C - Exception Handling

https://atcoder.jp/contests/abc134/tasks/abc134_c?lang=en

问题描述

You are given a sequence of length N: A 1 _1 1, A 2 _2 2, …, A N _N N. For each integer i between 1 and N (inclusive), answer the following question:

Find the maximum value among the N-1 elements other than A i _i i in the sequence.

Constraints

2≤N≤200000
1 ≤ leq ≤ A i _i i ≤ leq ≤ 200000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A1
:
AN

Output

Print N lines. The i-th line (1≤i≤N) should contain the maximum value among the N−1 elements other than A i _i i in the sequence.

Sample Input 1

Sample Output 1

4
3
4

The maximum value among the two elements other than A 1 _1 1, that is, A 2 _2 2 = 4 and A 3 _3 3 = 3, is 4.
The maximum value among the two elements other than A 2 _2 2, that is, A 1 _1 1 = 1 and A 3 _3 3 = 3, is 3.
The maximum value among the two elements other than A 3 _3 3, that is, A 1 _1 1 = 1 and A 2 _2 2 = 4, is 4.

Sample Input 2

2
5
5

Sample Output 2

5
5

题解小码匠

void coder_solution() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector a(n);
    vector dp(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        dp[i] = a[i];
    }
    
    sort(dp.begin(), dp.end());
    
    for (int i = 0; i < n; ++i) {
        if(a[i] == dp[n - 1]) {
            cout << dp[n - 2] << endl;
        } else {
            cout << dp[n - 1] << endl;
        }
    }
}

参考题解

累积和思路
- 从开头和结尾构造了两个数组
  - lft [i]: = 从 A [0] 到 A [i] 的最大值
  - rht [i]: = 从 A [i] 到 A [N-1] 的最大值
  - 如果这样做，第 i 个以外的最大值将是 max (lft [i -1], rht [i + 1])

int N, A[201010];
int lft[201010], rht[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
 
	rep(i, 0, N) lft[i] = A[i];
	rep(i, 1, N) chmax(lft[i], lft[i - 1]);
 
	rep(i, 0, N) rht[i] = A[i];
	rrep(i, N - 2, 0) chmax(rht[i], rht[i + 1]);
 
	rep(i, 0, N) {
		int ans = -1;
		if (0 < i) chmax(ans, lft[i - 1]);
		if (i + 1 < N) chmax(ans, rht[i + 1]);
		printf("%dn", ans);
	}
}

动态规划基础题(第4题): 此累积和非累积和

C/C++/C#相关栏目本月热门文章