問題：如果一個長度為N的陣列A在最多執行一次以下操作后可以不遞減，則稱該陣列 A 是偽排序的。
選擇一個i滿足1≤i≤N?1并交換A i和A i 1
給定一個陣列A，確定它是否是偽排序的。
輸入格式
第一行包含一個整數T - 測驗用例的數量。然后是測驗用例。
每個測驗用例的第一行包含一個整數N - 陣列A的大小。
每個測驗用例的第二行包含N個以空格分隔的整數A 1 , A 2 ,...,A N表示陣列 A。
輸出格式
對于每個測驗用例，如果陣列A是偽排序的，則輸出YES ，否則輸出NO。
您可以以大寫或小寫形式列印YES和NO的每個字符（例如，, ,yes將被視為相同）。yEsYes
約束：
- 1≤T≤1000
- 2≤N≤10 5
- 1≤Ai≤10 9
- 所有測驗用例的 N 總和不超過 2?10 5
樣本輸入 1：
3
5
3 5 7 8 9
4
1 3 2 3
3
3 2 1
樣本輸出 1：
YES
YES
NO
我的解決方案：
#include <stdio.h>
int main()
{
int T, N, ara[100000], count, i, j;
scanf("%d", &T);
for (i = 0; i < T; i )
{
scanf("%d", &N);
for (j = 0; j < N; j )
{
scanf("%d", &ara[j]);
}
count = 0;
for (j = 1; j < N; j )
{
if (ara[j] < ara[j - 1])
{
count ;
}
}
if (count <= 1)
{
printf("YES\n");
}
else if (count > 1)
{
printf("NO\n");
}
}
return 0;
}
但是，盡管我的代碼在給定的測驗用例中運行良好，但在某些測驗用例中出現錯誤。誰能幫我識別錯誤？
uj5u.com熱心網友回復：
如果你有 n 個數字ara，那么演算法將如下所示
#include <stdio.h>
int main() {
int failCount = 0, i = 1, n = 4;
int ara[4] = {2, 0, 3};
int prevMax = ara[0] - 1;
while ((failCount < 2) && (i < n)) {
if (ara[i - 1] > ara[i]) {
failCount ;
if ((i > 1) && (prevMax > ara[i])) failCount ;
}
prevMax = ara[i - 1];
i ;
}
printf("%d", failCount);
return 0;
}
我知道您不想全部閱讀，因此您需要在回圈期間閱讀數字，而不是在回圈之前閱讀所有數字，上面的代碼是用于說明邏輯的簡化代碼。
此外，您需要考慮示例，例如
3 1 2
其中 3 > 1 會增加計數器，但稍后您比較 1 < 2 并且看起來是正確的，但是 3 也大于 2。這是我的第二個if要解決的問題。
樣品測驗
2 0 1
uj5u.com熱心網友回復：
您的測驗會計算 2 個相鄰數字無序的情況。這還不足以解決問題。這是一個反例：
1
3
3 1 2
3 1 2產生 a countof1但需要 2 次交換。
一旦你檢測到一個無序的元素，你必須測驗將它與前一個元素交換是否能解決問題：
#include <stdio.h>
int main() {
int T = 0, ara[100000], count, i, j;
scanf("%d", &T);
for (i = 0; i < T; i ) {
int N = 0;
scanf("%d", &N);
for (j = 0; j < N; j ) {
ara[j] = 0;
scanf("%d", &ara[j]);
}
count = 0;
for (j = 1; j < N && count < 2; j ) {
if (ara[j] < ara[j - 1]) {
int temp = ara[j - 1];
ara[j - 1] = ara[j];
ara[j] = temp;
count ;
if (j > 1) {
j -= 2;
}
}
}
if (count <= 1) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
一旦識別出故障，您可以擺脫陣列并避免轉換剩余的數字：
#include <stdio.h>
int main() {
int T = 0, i, j;
scanf("%d", &T);
for (i = 0; i < T; i ) {
int N = 0, n1 = 0, n2 = 0, n3, count = 0, c, temp;
scanf("%d", &N);
if (N >= 2) {
scanf("%d%d", &n1, &n2);
if (n1 > n2) {
temp = n1;
n1 = n2;
n2 = temp;
count ;
}
for (j = 2; j < N; j ) {
n3 = 0;
scanf("%d", &n3);
if (n2 > n3) {
count ;
if (count > 1)
break;
if (n1 > n3) {
count ;
break;
}
n1 = n3;
} else {
n1 = n2;
n2 = n3;
}
}
}
/* read and discard the rest of the line */
while ((c = getchar()) != EOF && c != '\n')
continue;
if (count <= 1) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/466416.html