[HDOJ3418 Beautiful Dream]二分答案+判定 or 松弛

【题目大意】
给定n种玩具，他们分别有a[1]…a[n]个，如果一个人获得了m种不同的玩具，那么他就会高兴，问最多能让多少个人高兴。
【算法分析】
算法1:
二分答案，然后把a[i]比答案大的都变成答案。
然后判Sum(a[i])是否大于等于m*ans。如果是则可行，否则不可行。
算法2:
每次求和，然后和/m得到一个上界，然后把a[i]>Sum/m都变成Sum/m。
然后继续求，直到没有a[i]改变。

【其它】
还有O(n)的算法。不过没想出来= =
LCC这有，不过没看懂：http://hi.baidu.com/pojoflcc/blog/item/a5e757816511ccdb9123d9b4.html
然后郭神牛给了个提示，拍个序从大到小搞。能n lg n。
我还是没YY到。。。继续YY一下。想到了更新。
【CODE】
#include using namespace std;
typedef long long lld;
lld n,m,Sum;
lld a[155];

bool can(lld Limit){
Sum=0;
lld i;
for (i=1;i<=n;i++)
if (a[i]>Limit) Sum+=Limit;
else Sum+=a[i];
if (Sum>=m*Limit) return true;
return false;
}

int main(){
lld l,r,mid,i;
while (cin >> n >> m){
for (i=1;i<=n;i++) cin >> a[i];
l=0; r=1000000000*n;
while (l+1 mid=(l+r)/2;
if (can(mid)) l=mid;
else r=mid-1;
}
if (can(r)) l=r;
cout << l << endl;
}
return 0;
}