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

小码匠

发布于 2022-06-16 18:09:07

7180

文章被收录于专栏：小码匠和老码农小码匠和老码农

碎碎念

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

合集

动态规划、累积和、排序

题目地址

C - Exception Handling

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

问题描述

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 in the sequence.

Sample Input 1

Sample Output 1

4
3
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<int> a(n);
    vector<int> 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("%d\n", ans);
	}
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2022-05-23，如有侵权请联系 cloudcommunity@tencent.com 删除

input