Supposons que nous ayons une liste de N nombres et répétions l'opération suivante jusqu'à ce qu'il ne nous reste plus qu'un seul nombre: choisissez deux nombres consécutifs quelconques et remplacez-les par leur somme. De plus, nous associons à chaque opération une pénalité égale à la valeur du nouveau nombre et appelons la pénalité pour toute la liste comme la somme des pénalités de chaque opération.
Remarque: les nombres consécutifs signifient que leurs index dans le tableau sont consécutifs, pas que leurs valeurs sont consécutives. Par exemple, étant donné la liste [1, 2, 3, 4, 5], nous pourrions choisir 2 et 3 pour la première opération, ce qui transformerait la liste en [1, 5, 4, 5] et encourrait une pénalité de 5 Le but de ce problème est de trouver la pire pénalité possible pour une entrée donnée.
Contraintes: 1 â ‰ ¤ N â ‰ ¤ 10 ^ 6 1 â ‰ ¤ Ai â ‰ ¤ 10 ^ 7, où * Ai désigne le ième élément initial d'un tableau. La somme des valeurs de N sur tous les cas de test ne dépassera pas 5 * 10 ^ 6.
int getTotalTime(int[] arr) {}
Example arr = [4, 2, 1, 3] output = 23 First, add 4 + 2 for a penalty of 6. Now the array is [6, 1, 3] Add 6 + 1 for a penalty of 7. Now the array is [7, 3] Add 7 + 3 for a penalty of 10. The penalties sum to 23.
4 Réponses :
Je l'ai résolu comme ça mais je ne sais pas si c'est optimal ou non
static int getTotalTime(int[] arr) {
List<Integer> output = new ArrayList<>();
Arrays.stream(arr).forEach(output::add);
if (output.size() < 3) {
return output.stream().reduce((a, b) -> a + b).get();
}
int sum = 0;
List<Integer> max1 = new ArrayList<>();
max1.add(0);
for (int i = 2; i < output.size(); i++) {
if (output.get(i) + output.get(i - 1) > output.get(max1.get(0)) + output.get(max1.get(0) + 1)) {
max1 = new ArrayList<>();
max1.add(i - 1);
}else if (output.get(i) + output.get(i - 1) == output.get(max1.get(0)) + output.get(max1.get(0) + 1)) {
max1.add(i - 1);
}
}
sum = sum + output.get(max1.get(0)) + output.get(max1.get(0) + 1);
List newList = new ArrayList(output);
newList.set(max1.get(0), output.get(max1.get(0)) + output.get(max1.get(0) + 1));
newList.remove(max1.get(0) + 1);
int remainingSum = getTotalTime(newList);
for (int i = 1; i < max1.size(); i++) {
newList = new ArrayList(output);
newList.set(max1.get(i), output.get(max1.get(i)) + output.get(max1.get(i) + 1));
newList.remove(max1.get(i) + 1);
int nextRemainingSum = getTotalTime(newList);
if (nextRemainingSum > remainingSum) {
remainingSum = nextRemainingSum;
}
}
sum += remainingSum;
return sum;
}
static int getTotalTime(List<Integer> output) {
int sum = 0;
while (output.size() > 2) {
int max1 = 0;
for (int i = 2; i < output.size(); i++) {
if (output.get(i) + output.get(i - 1) > output.get(max1) + output.get(max1 + 1)) {
max1 = i - 1;
}
}
sum += output.get(max1) + output.get(max1 + 1);
output.set(max1, output.get(max1) + output.get(max1 + 1));
output.remove(max1 + 1);
}
return sum + output.stream().reduce((a, b) -> a + b).get();
}
Lorsque vous vous interrogez sur l'algorithme, vous pouvez expliquer en quoi consiste l'algorithme que vous implémentez dans ce programme. Inutile de saisir trop de détails.
C'est un problème gourmand. La clé derrière cela est de remarquer que nous devons toujours suivre la plus grande somme possible à chaque itération. Dans votre cas [4, 2, 1, 3] , la première plus grande somme est 6 , puis 7 puis 10 .
Le problème survient lorsque la plus grande somme apparaît plusieurs fois, par exemple [5, 3, 7, 1] , alors vous devez choisir s'il vaut mieux commencer par [5, 3] ou [7, 1] .
#include <bits/stdc++.h>
using namespace std;
int n = 6; //array size
int a[] = {2, 1, 7, 1, 5, 3}; //array
vector<pair<int, int>> v; //positions we will analyse
void analyse(){ //this method gets the positions with biggest sum
int sum = 0;
for(int i = 1; i < n; i++) sum = max(sum, a[i - 1] + a[i]);
for(int i = 1; i < n; i++) if(a[i - 1] + a[i] == sum) v.push_back(make_pair(i - 1, i));
}
int evaluate_penalty(int i, int j){ //given a position, this method finds
int l = i, r = j; //the biggest penalty starting there
int penalty = a[i] + a[j];
int val = penalty;
while(i != 0 || j != n - 1){
if(l > 0 && r < n - 1) {
if(a[l - 1] > a[r + 1]) l--;
else r++;
}
else if(l > 0) l--;
else r++;
val += (l != i ? a[l] : 0) + (r != j ? a[r] : 0);
penalty += val;
i = l; j = r;
}
return penalty;
}
int max_penalty(){ //this method finds the biggest penalty
v.clear(); //within all the possible starting positions.
analyse();
int maxPenalty = 0;
for(int i = 0; i < v.size(); i++){
maxPenalty = max(maxPenalty, evaluate_penalty(v[i].first, v[i].second));
}
return maxPenalty;
}
int main(){
cout<<max_penalty()<<endl;
return 0;
}
La complexité est O (n²) , MAIS dans la plupart des cas, ce sera O (n) . Étant donné que la plus grande somme entre deux nombres consécutifs est s , la complexité dépend du nombre de paires de nombres consécutifs somme s . S'il n'y en a qu'un (comme dans votre exemple [4, 2, 1, 3] , il se terminera en une itération, d'où O (n). Si le tableau est quelque chose comme [1, 1, 1, 1, 1, ..., 1] , il faudra O (n²).
Ouais, ça ressemble presque à ma solution. Je ne sais pas s'il y a une meilleure approche ou non, mais au moins cela confirme la mienne. Merci
Voici une solution optimisée en Javascript comprenant quelques cas de test. Le principe clé est que la pénalité la plus élevée peut être obtenue à chaque étape en ajoutant les deux plus grands éléments du tableau.
//Begin Solution
function getTotalTime(arr) {
function getTotal(a){
if(a.length==2)
return a[0]+a[1]
else{
const penalty = a[a.length-1]+a[a.length-2]
return penalty+getTotal([...a.slice(0,a.length-2),penalty])
}
}
return getTotal(arr.slice(0,arr.length).sort((a,b)=>a-b))
}
//End Solution
// These are the tests we use to determine if the solution is correct.
function printInteger(n) {
var out = '[' + n + ']';
return out;
}
var test_case_number = 1;
function check(expected, output) {
var result = (expected == output);
var rightTick = "\u2713";
var wrongTick = "\u2717";
if (result) {
var out = rightTick + ' Test #' + test_case_number;
console.log(out);
}
else {
var out = '';
out += wrongTick + ' Test #' + test_case_number + ': Expected ';
out += printInteger(expected);
out += ' Your output: ';
out += printInteger(output);
console.log(out);
}
test_case_number++;
}
var arr_1 = [4, 2, 1, 3];
var expected_1 = 26;
var output_1 = getTotalTime(arr_1);
check(expected_1, output_1);
var arr_2 = [2, 3, 9, 8, 4];
var expected_2 = 88;
var output_2 = getTotalTime(arr_2);
check(expected_2, output_2);
Il existe une solution meilleure et simple à ce problème en utilisant MaxHeap.
int getTotalPenalty (int[] arr) {
PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
for(int i = 0; i < arr.length; i++) {
q.add(arr[i]);
}
int totalP = 0;
while(q.size() > 1) {
int penality = q.poll() + q.poll();
totalP = totalP + penality;
q.add(penality);
}
return totalP;
}
Pourriez-vous publier tout le contenu de votre question? Les liens externes peuvent mourir et votre question serait incomplète.
Vous recherchez l'algorithme le plus rapide? Ou quel est votre objectif?