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

碎碎念

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

标签

• 累积和、排序

合集

• 动态规划、累积和、排序

题目地址

C - Exception Handling

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

问题描述

Input

Input is given from Standard Input in the following format:

代码语言：javascript复制

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

代码语言：javascript复制

3
1
4
3

Sample Output 1

代码语言：javascript复制

4
3
4

Sample Input 2

代码语言：javascript复制

2
5
5

Sample Output 2

代码语言：javascript复制

5
5

题解

小码匠

代码语言：javascript复制

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])
  • 从开头和结尾构造了两个数组

代码语言：javascript复制

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);
	}
}

input lines max output sample

0 人点赞