長100厘米的細長直杆子上有n隻螞蟻。它們的頭有的朝左，有的朝右。 每隻螞蟻都隻能沿着杆子向前爬，速度是1厘米/秒。 當兩隻螞蟻碰面時，它們會同時掉頭往相反的方向爬行。 這些螞蟻中，有1隻螞蟻感冒了。并且在和其它螞蟻碰面時，會把感冒傳染給碰到的螞蟻。 請你計算，當所有螞蟻都爬離杆子時，有多少隻螞蟻患上了感冒。
【資料格式】
第一行輸入一個整數n (1 < n < 50), 表示螞蟻的總數。
接着的一行是n個用空格分開的整數 Xi (-100 < Xi < 100), Xi的絕對值，表示螞蟻離開杆子左邊端點的距離。正值表示頭朝右，負值表示頭朝左，資料中不會出現0值，也不會出現兩隻螞蟻占用同一位置。其中，第一個資料代表的螞蟻感冒了。
要求輸出1個整數，表示最後感冒螞蟻的數目。
例如，輸入：
3
5 -2 8
程式應輸出：
1
再例如，輸入：
5
-10 8 -20 12 25
程式應輸出：
3
資源約定：
峰值記憶體消耗 < 256M
CPU消耗 < 1000ms
解題思路
使用隊列儲存所有螞蟻,為螞蟻的位置進行排序,螞蟻離開隻會發生在兩端,當螞蟻出隊時記錄是否感冒.
?
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 | #include <iostream> #include <algorithm> #include <vector> typedef struct { int pos; bool isGm; } my; int abs ( int a) { return a > 0 ? a : -a; } bool cmpMy(my a, my b) { return abs (a.pos) < abs (b.pos); } int getNextPos( int now) { //return now > 0 ? now + 1 : now - 1; return now + 1; } int main() { unsigned count, gmCount(0); std::vector<my> data; my t = {0, false }; std::cin >> count; do { std::cin >> t.pos; data.push_back(t); } while (--count); data[0].isGm = true ; sort(data.begin(), data.end(), cmpMy); while (data.size()) { for (unsigned i(0); i != data.size(); ++i) { if ( abs (data[i].pos) == 100 || data[i].pos == 0) { if (data[i].isGm) ++gmCount; if (i == 0) { data.erase(data.begin()); } else { data.erase(data.end() - 1); } --i; continue ; } //std::vector<my>::iterator prev = i - 1; int next = i + 1; int prev = i - 1; int nextPos = getNextPos(data[i].pos); if (data[i].pos > 0) { if (next != data.size()) { if ( abs (nextPos) == abs (data[next].pos)) { data[i].pos *= -1; data[next].pos *= -1; if (data[i].isGm || data[next].isGm) { data[next].isGm = true ; data[i].isGm = true ; } goto end; } } } else { if (prev != -1) { if ( abs (nextPos) == abs (data[prev].pos)) { data[i].pos *= -1; data[prev].pos *= -1; if (data[i].isGm || data[prev].isGm) { data[prev].isGm = true ; data[i].isGm = true ; } goto end; } } } data[i].pos = nextPos; end:; } } std::cout << gmCount << std::endl; return 0; } |
