长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; } |
