ahmedarifhasan Ответов: 1

Это вопрос от codechef, Ссылка:https://www.codechef.com/ZCOPRAC/problems/ZCO14003


я не знаю, почему мой ответ отвергается.
Страница Конкурса | CodeChef[^]

Что я уже пробовал:

my code:
#include<stdio.h>
int main()
{
int j,i,N,c;

long long int a[5000],revmax[5000];
scanf("%d",&N);

for(i=0;i<N;i++)
 scanf("%lld",&a[i]);

for(i=0;i<N;i++)
 { 
   for(j=0;j<N-1;j++)
     { 
       if(a[j]>a[j+1])
       {
         c=a[j];
         a[j]=a[j+1];
         a[j+1]=c;
       }
     }
  }


for(i=0;i<N;i++)
 {
  revmax[i]=(N-i)*a[i]; 
 }

for(i=0;i<N;i++)
 {
   for(j=0;j<N-1;j++)
   {
     if(revmax[j]>revmax[j+1])
       {
        c=revmax[j];
        revmax[j]=revmax[j+1];
        revmax[j+1]=c;
       }
           
   }
 }

printf("%lld",revmax[N-1]);
}

1 Ответов

Рейтинг:
0

OriginalGriff

Есть два варианта:
1) Он дает неверный ответ.
2) для получения ответа требуется слишком много времени.

Не представив его и не увидев, что их данные делают с вами, трудно сказать.

Но при предположении (предполагая, что он производит правильное число, которое, как я предполагаю, вы тестировали локально) Я бы сказал, что у него мало времени, потому что ваш алгоритм сортировки настолько неэффективен. У вас есть потенциально 5x105 входные данные: вы действительно считаете, что базовая сортировка пузырьков (выполняемая дважды) является лучшим решением?


ahmedarifhasan

но я только начал программировать 3 месяца назад, и что касается сортировки, то это единственный метод, о котором я думал, разве этот метод пузырьковой сортировки не работает для огромных чисел? я имею в виду, как я могу сделать свою программу более эффективной?

OriginalGriff

- не могли бы вы просто отредактировать и показать мне решение, Пожалуйста"
Нет! :смейтесь:
Это "соревнование", и как таковое считается домашним заданием - и мы не делаем этого для вас, потому что вы ничего не узнаете из него.

Это упражнение в вашем мышлении, а не в моем. И если вы хотите быть хорошим в этом (и вы, вероятно, делаете, иначе вы не пробовали бы упражнения, подобные этому), то очень важно, чтобы вы пытались думать о возможных решениях, а также об "очевидном".

Задумайтесь: зачем вы вообще сортируете элементы? А тебе это нужно? Какие еще способы вы могли бы использовать?

Да, и кстати: ваш вид не будет работать должным образом. Почему ваш входной массив длинный-длинный? Что произойдет, если вы попытаетесь отсортировать элементы, которые не помещаются в целое число?

ahmedarifhasan

о! я понимаю, мне не следовало просить решения. :)

таким образом, в принципе, это означает, что существует другой способ решения этой проблемы, кроме сортировки. И еще одна вещь, вы рекомендуете мне делать такие задачи, потому что я еще не начал указатели.

OriginalGriff

Вам не нужны указатели - хотя они облегчили бы жизнь, поскольку можно использовать malloc.

Как бы вы сделали это вручную?

ahmedarifhasan

могу ли я получить вашу личную контактную информацию, например, учетную запись fb, пожалуйста.

OriginalGriff

Нет - я получаю вполне достаточно писем каждый день, как это спасибо! :смеяться:

ahmedarifhasan

лол! :)

ahmedarifhasan

я думал, что если я буду сортировать, то это станет проще, потому что нам нужно суммировать наибольшее число один раз, а затем следующее по величине число дважды, поэтому я думал, что сортировка уменьшит количество строк кода.

OriginalGriff

Нет-нет. Подумайте об этом. Речь идет о разработке максимального дохода, а не самой высокой стоимости единицы.
Если у вас есть один человек, готовый заплатить 100 000 долларов за копию, и 200 000 человек, готовых заплатить 1 доллар, какую цену вы устанавливаете? Сколько вы можете получить за каждую возможную цену?

ahmedarifhasan

ого! потрясающе! большое вам спасибо!

OriginalGriff

Ты должен прочитать вопрос, чувак! :смеяться:

ahmedarifhasan

ну, очевидно, чувак за 1 доллар.

OriginalGriff

Да - потому что за 100 000 долларов заплатит только один парень, так что вы заработаете только 100 000 долларов.
За 1 доллар вы получаете 200 001 доллар, потому что все будут платить.
Следовательно, вклад, который они дают 30, 20, 53 и 14, давая результат 60 - один, заплатит 53, два человека готовы заплатить 30, Три заплатят 20, а 4 заплатят 14.
Таким образом, доходы составляют 60, 60, 53 и 56 для этого примера. Но еще один парень, готовый заплатить 15, изменил бы максимальный доход до 70 по цене 14.
Так что проблема не столько в сортировке, сколько в группировке.

ahmedarifhasan

подождите, я этого не понял, если другой парень заплатит 15, как это станет 70?

OriginalGriff

5 * 14 = 70
4 * 15 = 60
3 * 20 = 60
2 * 30 = 60
1 * 53 = 53

ahmedarifhasan

спасибо, чувак! я действительно уважаю то, как вы отвечали на каждый вопрос!

OriginalGriff

Всегда пожалуйста!