SRM 646 DIV1 Easy - TheConsecutiveIntegersDivOne x○
問題
・複数の数字が与えられる。
・ｋ個の数字が連続して並ぶようにしたい。
・数字を１つ動かすのにコストが１かかるとき、最小のコストを求める。
解き方
・数字を連結させるための最小コストを求めるとき、
少なくともひとつの数字の場所は固定されていることがわかれば解ける。
・あとはｋ個の連続する数字の範囲全てについて、そのうち全ての数字を固定した場合の
最小コストを求めればよい。
コード
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 TheConsecutiveIntegersDivOne {
public: int find(vector<int> numbers, int k) {
int n=numbers.size();
sort(all(numbers));
int ret=1e+9;
for(int i=0;i+k-1<n;i++){
for(int j=i;j<=i+k-1;j++){
int cost=0;
for(int l=i;l<=i+k-1;l++)cost+=abs(numbers[l]-numbers[j]-(l-j));
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 TheConsecutiveIntegersDivOne {
public: int find(vector<int> numbers, int k) {
int n=numbers.size();
sort(all(numbers));
int ret=1e+9;
for(int i=0;i+k-1<n;i++){
for(int j=i;j<=i+k-1;j++){
int cost=0;
for(int l=i;l<=i+k-1;l++)cost+=abs(numbers[l]-numbers[j]-(l-j));
ret=min(ret,cost);
}
}
return ret;
}
};
