E
E - NYOJ
suma/sumb 与 mid的比较，可以转化为（b1 + b2 + ……+ bn-1) * mid 与(a1 + a2 + …… + an-1)
再转化为 a1 - b1 * mid + a2 - b2 * mid + …… +an-1 - bn-1 * mid
关于此题条件反射：条件是二分答案，题目出现小数，反射是套用浮点数二分模板
写题时把所有变量都定义成了浮点型，结果ce
//invalid types 'double [100000][double]' for array subscript
//数组下标不能为浮点型
关于此题为什么没有特别处理四舍五入：未知
#include <iostream> #include <algorithm> using namespace std; const int N = 1e5; typedef double ll; double a[N],b[N],sum[N]; int n,k; bool check(double mid){ double cnt = 0; //for(double i = 0;i < n;i++){ …… } //invalid types 'double [100000][double]' for array subscript //数组下标不能为浮点型 for(int i = 0;i < n;i++){ sum[i] = a[i] - mid * b[i]; cnt += sum[i]; } sort(sum,sum+n); for(int i = 0;i < k ;i++){ cnt -= sum[i]; } // cout << "sum=" << cnt << endl; if(double(cnt) >= 0)return true; else return false; } int main(){ while(scanf("%d %d",&n,&k)){ if(n == 0 && k == 0) break; for(int i = 0;i < n;i++){ scanf("%lf",&a[i]); } for(int i = 0;i < n;i++){ scanf("%lf",&b[i]); } double l = 0,r = 1; while(r - l > 0.00001){ double mid = (l + r) /2 ; if(check(mid))l = mid; else r = mid; } printf("%.0lf\n",l*100); } return 0; }
C
重做此题时一直re，原因是多组输入scanf少了个~，太久没用这种写法，不熟练了
还有就是做题时纠结的一个点：int 能否与 long long比较，经过检验，答案是可以
#include <iostream> using namespace std; typedef long long ll; const int N = 1e5 + 10; ll n,k,a[N]; bool check(ll mid){ ll cnt = 0; for(int i = 0;i < n;i++){ if(a[i] - mid > 0) cnt += (a[i] - mid + k - 1 - 1) / (k - 1); } if(cnt <= mid) return true ; else return false; } signed main(){ while(~scanf("%lld",&n)){ //int 可以和long long 比较 ll maxn = 0; for(int i = 0;i < n;i++){ scanf("%lld",&a[i]); maxn = max(maxn ,a[i]); } scanf("%lld",&k); if(k == 1) { printf("%lld",maxn); continue; } ll l = 0,r = maxn + 1; while(l < r){ ll mid = (l + r) >> 1; if(check(mid))r = mid; else l = mid + 1; } printf("%lld",r); } return 0; }
明天学学筛法好了，在二分这块停滞太久了
