网易编程答案
第一题反转队列100% 第二题存活时间100% 第三题疯狂排队90%
第一第二太简单不说,
第三题想出来一个笨拙的贪心法,最后修改好了,可惜考试结束。这里贴出来。
测试用例:
3
1 1 10
3
1 9 10
4
10 10 10 1
6
10 10 10 1 1 1
5
10 10 10 1 1
#include <iostream> #include<string> #include<algorithm> #include<functional> #include<vector> #include<set> #include<sstream> #include<deque> using namespace std; void print(deque<int> &dq) { for (int n : dq) { cout << n << ' '; } cout << endl; } int max_crazy(deque<int> &dq) { //print(dq); int result = 0; for (int i = 1; i < dq.size(); i++) { result += abs(dq[i] - dq[i - 1]); } return result; } int main() { freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int n; int temp; while (cin >> n) { deque<int> dq; deque<int> dq2; for (int i = 0; i < n; i++) { cin >> temp; dq.push_back(temp); } sort(dq.begin(), dq.end()); dq2.push_back(dq.back()); dq.pop_back(); while (dq.size()) { //两次从队列前 if (dq.size()) { abs(dq.front() - dq2.front()) > abs(dq.front() - dq2.back()) ? dq2.push_front(dq.front()) : dq2.push_back(dq.front()); dq.pop_front(); } if (dq.size()) { abs(dq.front() - dq2.front()) > abs(dq.front() - dq2.back()) ? dq2.push_front(dq.front()) : dq2.push_back(dq.front()); dq.pop_front(); } //两次从队尾 if (dq.size()) { abs(dq.back() - dq2.front()) > abs(dq.back() - dq2.back()) ? dq2.push_front(dq.back()) : dq2.push_back(dq.back()); dq.pop_back(); } if (dq.size()) { abs(dq.back() - dq2.front()) > abs(dq.back() - dq2.back()) ? dq2.push_front(dq.back()) : dq2.push_back(dq.back()); dq.pop_back(); } } cout << max_crazy(dq2) << endl; } }