ACM 竞赛高校联盟 练习赛 第二场 BC

B.

题解：

枚举约数即可，判断n个数能否填约数的整数倍

 

#include 
#include 
#include 
using namespace std;
typedef long long LL;
int main(){LL T, n, m;cin>>T;while(T--){cin>>n>>m;LL Max = 0;for(LL i = 1; i*i <= m; i++){if(m % i == 0){if(m/i >= n) Max = max(Max, i);if(i >= n) { Max = max(Max, m/i); break; }}    }cout<endl;}
}

 

C.

这题暴力贪心就可以过了orz

不过也有二分+动态维护凸包的神奇做法，这里不多说了

#include 
#include 
#include 
using namespace std;
const int maxn = 1e4 + 10;
int a[maxn], b[maxn], f[maxn];
int main(){int T, n, k;cin>>T;while(T--){cin>>n>>k;memset(f, 0, sizeof(f));for(int i = 1; i <= n; i++) scanf("%d %d", &b[i], &a[i]);double ans = 0;long long w = 0, v = 0, t = 0;for(int i = 1; i <= k; i++){ans = 0;    for(int j = 1; j <= n; j++){if(f[j]) continue;if( (double) (w + a[j])/(v + b[j]) > ans){ans = (double) (w + a[j])/(v + b[j]);t = j;}}w += a[t];v += b[t];f[t] = 1;}printf("%.4f
", (double)w/v);}
}