SRM 634 Div2 Medium ShoppingSurveyDiv2

問題

SRM 634 - TopCoder Wiki

問題を説明するのがちょっと難しい. N人がM個の商品についてレビューする. s[i]は商品iについて好意的に評価している人の数を表す. 全ての商品について好意的に評価している人をbig shopperと呼ぶ. 考えられる場合の内,big shopperの最小人数を答える問題.

解答

  • big shopperの数をx人とした時,レビューが成り立つかどうかの判定方法を考える.
  • big shopperは全てに好意的に評価するので,残りの評価数は各iについてs[i]-xとなる.
  • 残りの人で,全てに好意的に評価せず,評価数を埋めることが出来れば,big shopperがx人でレビューが成り立つ.
  • 可能な限り評価しようとすると,各評価者はM-1個に関して評価を行う.
  • 評価できる最大数が残りの評価数を超えていれば成り立つ.
  • x=0から徐々に増やしていって初めて成り立った時のxを返す.
class ShoppingSurveyDiv2
{
public:
  int minValue(int N, vector <int> s)
    {
      int bshopper;
      int i, j;
      int n = s.size();
      for (bshopper = 0; bshopper <= 100; bshopper++){
        int count = 0;
        for (i = 0; i < n; i++) {
          count += (N - bshopper) - max(0, (s[i] - bshopper));
        }
        if ((N - bshopper) <= count) return bshopper;
      }
      return bshopper;
    }
};