SRM 645 DIV2 Middle - ConnectingCars (○)
問題
・一列の道路に車が複数あり、その車の先頭位置とその長さが与えられる。
・全ての車を連結したいとき、必要となる最小の移動距離を求める。
解き方
・車を連結させるとき、そのうち一つの車の位置は固定となることがわかれば解ける。
・あとは実装の問題。
ある車を固定した時の移動距離を、左側にあるものの計算と右側にあるものの計算を分けて、
近い順に行っていけばシンプルに実装できる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class ConnectingCars {
public: long long minimizeCost(vector<int> positions, vector<int> lengths) {
int n=positions.size();
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(positions[i],lengths[i]));
sort(all(p));
long long ret=1e+18;
FORE(i,0,n){
long long cost=0;
long long pos=p[i].first+p[i].second-1;
FORE(j,i+1,n){
cost+=abs(pos+1-p[j].first);
pos+=p[j].second;
}
pos=p[i].first;
for(int j=i-1;j>=0;j--){
cost+=abs(pos-p[j].first-p[j].second);
pos-=p[j].second;
}
ret=min(ret,cost);
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class ConnectingCars {
public: long long minimizeCost(vector<int> positions, vector<int> lengths) {
int n=positions.size();
vector<pair<int,int> > p;
FORE(i,0,n)p.push_back(make_pair(positions[i],lengths[i]));
sort(all(p));
long long ret=1e+18;
FORE(i,0,n){
long long cost=0;
long long pos=p[i].first+p[i].second-1;
FORE(j,i+1,n){
cost+=abs(pos+1-p[j].first);
pos+=p[j].second;
}
pos=p[i].first;
for(int j=i-1;j>=0;j--){
cost+=abs(pos-p[j].first-p[j].second);
pos-=p[j].second;
}
ret=min(ret,cost);
}
return ret;
}
};
