白駿11399号:ATM

リンク:https://www.acmicpc.net/problem/11399

問題を読む

を選択します.ギリシャ探索問題.
小さい順に並べてこそ、最高価格が得られます.始めましょう.では、これはどのようにして小さな順序で並べ替えることができますか?これは資料構造の問題です.

コード#コード#

Ver 1.

#include<iostream>
#include<algorithm>
using namespace std;

int arr[1001], sum[1001], result[1001];
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr,arr+N);
	result[0] = sum[0] = arr[0];
	for (int i = 1; i < N; i++) {
		sum[i] = arr[i] + sum[i - 1];
		result[i] = result[i - 1] + sum[i];
	}
	cout <<result[N-1];
	return 0;
}

Ver 2.

#include<iostream>
#include<algorithm>
using namespace std;

int arr[1001], sum[1001];
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	sort(arr,arr+N);

	sum[0] = arr[0];
	int tmp = sum[0];
	for (int i = 1; i < N; i++) {
		tmp = sum[i] = arr[i] + tmp;
		sum[i] = sum[i - 1] + sum[i];
	}
	cout <<sum[N-1];
	return 0;
}

ぶんせき

sortはアルゴリズムライブラリを借りています.

result[0] = sum[0] = arr[0];
for (int i = 1; i < N; i++) {
	sum[i] = arr[i] + sum[i - 1];
	result[i] = result[i - 1] + sum[i];
}

この部分はフィボナッチ数列のように近づくことができます.でもresult配列を使わなければいいんですよね?考えてみましょう.
だから.

sum[0] = arr[0];
int tmp = sum[0];
for (int i = 1; i < N; i++) {
	tmp = sum[i] = arr[i] + tmp;
	sum[i] = sum[i - 1] + sum[i];
}

tmp変数を使用しました.これは当然ですが、int変数を宣言するのは1001配列を宣言するよりも有効です.