Пользователь вводит n чисел, за которыми следует следовать в следующей строке, а затем вводит n чисел a1, a2, ..., an.Эти цифры высоты некоторых гор.Набор этих чисел «ПРИНИМАЕТСЯ», если есть только один максимум или минимум.например, «1 2 3 2 1», имеет только один максимум, который равен 3. Также «1 2 3 4» имеет один максимум.но «1 10 9 8 7 6 5 6 7» неприемлемо, поскольку оно имеет два максимума (10 и 7) или два минимума (1 и 5).
Другими словами, набор является приемлемым, если итолько если он находится в одной из следующих форм:
a1 <= a2 <= a3 ... <= ai> a (i + 1)> ...> an
или
a1> = a2> = a3 ...> = ai
Я должен представить ответ в системе судьикоторый проверяет это с неизвестными контрольными случаями. Использование любого типа массива или вектора полностью запрещено.
Мое решение таково:
//C code.
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,temp;
scanf("%d",&n);
if (n==1)
{
int l;
scanf("%d",&l);
printf("Yes");
}
else
{
int a,b;
int last;
int changes =0;
int dec =0 , inc =0; //flag: checking if the set is incremental or decremental till now
scanf("%d %d",&a,&b);
if (a>b)
{
dec=1;
}
else if (a<b)
{
inc = 1;
}
else
{
inc =1;
dec = 1;
}
last = b;
for (int i =2;i<n;i++)
{
scanf("%d",&temp);
if (temp>last && dec==1)
{
inc = 1;
dec= 0;
changes++;
}
if (temp<last && inc==1)
{
inc =0;
dec=1;
changes++;
}
if (!(inc==1 && dec==1) && temp == last)
{
changes++;
}
last = temp;
last = temp;
}
if (changes <=1)
{
printf("Yes");
}
else
{
printf("No");
}
}
return 0;
}
Он получает правильный ответ для примеров, которые в вопросено это не удается на некоторых неизвестных тестовых случаях.Есть идеи как это исправить?Может ли кто-нибудь дать мне контрольный пример, который не решен прямо в этом коде?
P.1: я добавил
if (!(inc==1 && dec==1) && temp == last)
{
changes++;
}
, и он принял один из неудачных контрольных примеров, но все еще один остается.
P.2:
Это мой другой алгоритм, который не срабатывает в некоторых тестовых случаях, но судья принимает свои ответы в случае неудачных тестов в первом:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
int inc=0;
int dec=0;
int peak=0;
int valley=0;
int last = -1;
int a;
scanf("%d",&n);
for (int i =0;i<n;i++)
{
if (last!=-1)
{
last =a;
}
scanf("%d",&a);
if (last!=-1)
{
if (a>last)
{
if (!(inc==1))
{
valley++;
inc =1;
dec=0;
}
}
if (a<last)
{
if (!(dec==1))
{
peak++;
dec=1;
inc =0;
}
}
}
last =0;
}
if (valley<=1 && peak<=1)
{
// printf("valley: %d , peak:%d",valley,peak);
printf("Yes");
}
else
{
printf("No");
}
return 0;
}
С.3
Новый алгоритм:
#include <stdio.h>
#include <stdlib.h>
int main()
{
long long int n,temp;
scanf("%lld",&n);
if (n==1)
{
long long int l;
scanf("%lld",&l);
printf("Yes");
}
else
{
long long int a,b;
long long int last;
long long int changes =0;
int dec =0 , inc =0; //flag: checking if the set is incremental or decremental till now
scanf("%lld %lld",&a,&b);
if (a>b)
{
dec=1;
}
else if (a<b)
{
inc = 1;
}
else
{
inc =1;
dec = 1;
}
last = b;
for (long long int i =2;i<n;i++)
{
scanf("%lld",&temp);
if (temp>last && dec==1)
{
inc = 1;
dec= 0;
changes++;
}
if (temp<last && inc==1)
{
inc =0;
dec=1;
changes++;
}
if (changes>=1 && temp == last)//new change
{
changes+=100;
}//end of new change
last = temp;
}
if (changes <=1)
{
printf("Yes");
}
else
{
printf("No");
}
}
return 0;
}