|
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MX = 1005;
int leadingZero(string s) {
int cnt = 0, len = s.length();
for (int i = 0; i < len; i++) {
if (s[i] != '0')
return cnt;
cnt++;
}
return cnt;
}
struct Num {
bool neg = false;
int len;
int ar[MX];
string str;
Num() {}
Num(string s) {
str = s;
if (s[0] == '-') {
neg = true;
s = s.substr(1);
}
s = s.substr(leadingZero(s));
len = s.length();
for (int i = 0; i < len; i++) {
ar[i] = s[i] - '0';
}
}
bool less(Num& b) {
if (!b.neg && neg)
return true;
else if (b.neg && !neg)
return false;
else if (neg && b.neg) {
this->neg = false;
b.neg = false;
bool r = !(this->less(b));
this->neg = true;
b.neg = true;
return r;
} else if (len < b.len)
return true;
else if (len > b.len)
return false;
for (int i = len - 1; i >= 0; i--) {
if (b.ar[i] > ar[i])
return true;
}
return false;
}
};
Num ar[1001];
int main(void) {
ios::sync_with_stdio(false);
int n;
while (cin >> n) {
string s;
for (int i = 0; i < n; i++) {
cin >> s;
ar[i] = s;
}
std::sort(ar, ar + n, [](Num& a, Num& b) { return a.less(b); });
for (int i = 0; i < n; i++) {
cout << ar[i].str << endl;
}
}
}
|
上面的是程式碼，自己測試都沒問題，但是船上去 SIGSEGV (記憶體區段錯誤)
把 sort(ar, ar + n, ... 改成 sort(ar, ar + n - 1, ... 就不會 RE 了
雖然不知道為什麼
但我知道這算出來答案會是錯的
基本上本題會拿到 RE(尤其是向樓主一樣「記憶體區段錯誤」) ,
其主要原因通常在於對於大數 小於(以樓主的利就是 less() ) 定義出錯,
所以導致 sort() 在比較時產生矛盾而出錯~
樓主在定義 less() 時有3個問題:
1. 你儲存數字在 ar[0]~ar[len-1] 中的順序是 從最高位→最低位 ,
但你在 less() 最後比較(同號且同位數)時比較的順序卻是 ar[len-1]~ar[0]
導致先比較最低位而錯誤
EX: *this=12、b=21 會判斷成 b 比較小而回傳 false
2. 在最後比較(同號且同位數)的迴圈中,
少考慮了當 b.ar[i] < ar[i] 時就能確定 b < this (要return false) 了,
若更後面的位數 ar[i] < b.ar[i] 會導致判斷錯誤~
EX: *this=21、b=12 會判斷成 *this 比較小而回傳 true
3. 當 neg && b.neg (同為負數) 時,
並非將結果反轉就好,
要考慮到相等的時候應該要回傳false, (因為定義的是小於, 所以相等要回傳false)
但被反轉後會變成回傳true而錯誤
EX: *this=12、b=12 會判斷成 *this 比較小而回傳 true
理論上來說 1. 會造成 WA 但不會 RE ,
至於 2. 和 3. 會造成 WA 或 RE ,
但經過測試只要修改 3. 就能過了... = =" (錯愕
看來這題的測資其實沒有出得很好 (X
以上希望有幫助到樓主~ OwO
3. 當 neg && b.neg (同為負數) 時,
並非將結果反轉就好,
要考慮到相等的時候應該要回傳false, (因為定義的是小於, 所以相等要回傳false)
但被反轉後會變成回傳true而錯誤
EX: *this=12、b=12 會判斷成 *this 比較小而回傳 true
3. 應該沒差吧
sort 在 compare 函式回傳 true 時會交換，false 時不會交換
實際上相等時有沒有交換都不會影響答案
回應樓上的:
當然有差呀,
「sort() 在 compare() 函式回傳 true 時會交換，false 時不會交換」 ,
以上只是描述 compare() 作用的結果而已,
這並不代表 compare() 只用於判斷兩者是否要交換而已,sort() 內部有著指針在記錄當前位置, (可以想像成 for(int i = 0; a[i]<a[j]; i++) 的 i 一樣)
當指針連續移動時勢必要判斷何時停下來, (可以想像成 for(int i = 0; a[i]<a[j]; i++) 的 a[i]<a[j] )
當你的小於(也就是 compare() )定義出問題時(好比 a[i]==a[j] 時回傳 true )就會造成指針超過預期的範圍,
比較好的情況只是位置出錯 WA,
或者是會形成無窮迴圈導致 TLE,
嚴重一點就會導致指針超過陣列(或容器)範圍而超過可以存取的記憶體位置導致 RE ~
另外我也說了,
測試的結果 3. 是真的會有影響的,
如果真的不相心有差的話,
看你是有 AC 本題的,
何不親手嘗試看看使你程式中的 compare() 更改成當 a==b 時回傳 true 看看會如何~