問題
http://community.topcoder.com/stat?c=problem_statement&pm=13858&rd=16511
解き方
Dが1000までなので、Dを固定することで解けそう。
ただ、Dをできるだけ小さくするということは、並べ方は以下の通り
一意に定まる。
要はh[i]の小さい順に0,1,2,3,4...とすると、単に0から左右に順に並べていけば良い。
3 1 0 2 4...となる。
コード
class FoxesOfTheRoundTable {
public: vector<int> minimalDifference(vector<int> h) {
int n=h.size();
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(h[i],i));
sort(all(p));
vector<int> ans;
int end = n%2 ? n-2 : n-1;
for(int i=end;i>0;i-=2)ans.push_back(p[i].second);
for(int i=0;i<n;i+=2)ans.push_back(p[i].second);
return ans;
}
};
public: vector<int> minimalDifference(vector<int> h) {
int n=h.size();
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(h[i],i));
sort(all(p));
vector<int> ans;
int end = n%2 ? n-2 : n-1;
for(int i=end;i>0;i-=2)ans.push_back(p[i].second);
for(int i=0;i<n;i+=2)ans.push_back(p[i].second);
return ans;
}
};