河北省住房和城乡建设厅的网站,做网站的地方,无需本金十分钟赚800,网站公司的利润在哪里链接#xff1a;
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 262144K#xff0c;其他语言524288K
64bit IO Format: %lld题目描述 输入描述:
输入包含t组数据 第一行一个整数t 接下来t行每行两个整数x,y 输出描述: 每组数据输出一行一个…链接
时间限制C/C 1秒其他语言2秒
空间限制C/C 262144K其他语言524288K
64bit IO Format: %lld题目描述 输入描述:
输入包含t组数据 第一行一个整数t 接下来t行每行两个整数x,y 输出描述: 每组数据输出一行一个整数表示答案。 示例1 输入 复制
5
4 8
7 6
8 10
100 4555
45465 24124输出 复制
2
2
3
50
13917备注: 1t10000 1x,y1e9
题解
两个做法一个三分一个贪心
三分的做法 我们都知道 二分查找 适用于单调函数中逼近求解某点的值。 如果遇到凸性或凹形函数时可以用三分查找求那个凸点或凹点。 假设A装备做了m件B装备做了n件我们固定m来求n nmin( (x-2m)/4 , y-3m )就是看做完m剩下的材料还能做多少个n然后返回nm不断三分求出nm的峰值即最大值
代码
#includebits/stdc.h
using namespace std;
int x,y;
int check(int n){return nmin((x-2*n)/4,y-3*n);
}
int main(){int T;scanf(%d,T);while(T--){cinxy;int l0;int rmin(x/2,y/3);//目前 的x和y最多能做多少个m while(lr){int mid1l(r-l)/3; int mid2r-(r-l)/3;if(check(mid1)check(mid2))rmid2-1;else lmid11;}printf(%d\n,check(l));}return 0;
}贪心的做法
1.材料a特别多时尽量用a来合成装备2满足a4bb为多少就可以做多少件 2材料b特别多时尽量用b来合成装备1要满足3a2*ba为多少就可以做a/2件 3.当两者差不多时我们结合题目中两个式子2a3b1,4ab1,我们可以得到a1/5,b1/5,也就是合成一件装备ab必须是5的倍数而且观察式子a还必须是偶数。 所以如果a不是偶数或者(ab)不是5的倍数结果就要减一 相当于去除多余的材料构成a为偶数ab为5倍数的情况
代码
#include bits/stdc.h
#define ll long long
using namespace std;
int t;
ll a,b;
int main() {cint;while(t--) {cinab;if(a(b2)) printf(%lld\n,b);else if(a*3(b1)) printf(%lld\n,(a1));else {ll sum(ab)/5;if(a1(ab)%50) --sum;printf(%lld\n,sum);}}
}
