SRM 634 DIV1 Easy - ShoppingSurveyDiv1 (×)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13455&rd=16077
・N人の客がいて、各商品を多くて１つ買うことができる。
・また、K種類以上の商品を買うBig Shopperがいる。
・商品iを買った人数s[i]がわかっているとき、Big Shopperは最低何人いるか求める。
解き方
・問題文をミスリードしてしまった。
・貪欲法で、Big Shopperが０人から増やしていきその場合に条件が成立するか
確かめればよい。
・確かめ方は、Big Shopperが存在するとき
買う種類はK以上であればよいので全部の商品を買うことにする。
このとき、残った値が（N-Big Shopperの数）×（K-1）以下であればよい。
コード
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 ShoppingSurveyDiv1 {
public: int minValue(int N, int K, vector<int> s) {
int n=s.size();
FORE(i,0,N){
int left=0;
FORE(j,0,n)if(s[j]>i)left+=s[j]-i;
if(left<=(N-i)*(K-1))return i;
}
return N;
}
};
#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 ShoppingSurveyDiv1 {
public: int minValue(int N, int K, vector<int> s) {
int n=s.size();
FORE(i,0,N){
int left=0;
FORE(j,0,n)if(s[j]>i)left+=s[j]-i;
if(left<=(N-i)*(K-1))return i;
}
return N;
}
};
