SRM 340 DIV1 Easy - ProblemsToSolve ××○

SRM 340 DIV1 Easy - ProblemsToSolve ××○

19:09

問題


http://community.topcoder.com/stat?c=problem_statement&pm=7504&rd=10664

・各問題について、その楽しさの値が与えられる。
・最初は０番目の問題を解く。その後、次の問題かその次の問題を選んでいく。
・選んだ問題の楽しさの値の最小と最大の差が、指定された値より大きくなればそこで終了。そうでなければ、全ての問題を解かなければいけない。

このとき、解かなければならない問題の最小値を求める。


解き方


問題数が最大５０なので、全探索で解けない。

問題の条件より、ある２つを選んだときその差が指定値より大きければ終了になる。

そのため全ての２つの組み合わせの中から、その差が指定値より大きくなるもの全てについて最小値を求めて更新していけばよい。

コード


class ProblemsToSolve {

public: int minNumber(vector<int> p, int variety) {
int n=p.size();
int ret=n;

FORE(i,0,n)FORE(j,i+1,n){
if(abs(p[j]-p[i])>=variety)ret=min(ret,(i+3)/2+(j-i+1)/2);
}

return ret;
}

};

Share this

Google Facebook Twitter More

Related Posts