做网站的系统设计,网站开发运营经理,百度搜索广告投放,网站开发属于软件开发服务吗冶炼金属
学习了b站Turing_Sheep的思路 一、暴力模拟 思路#xff1a; b[i] a[i] / v b[1] a[1] / v b[2] a[2] / v .... b[n] a[n] / v 以上列举中v要满足所有的记录#xff0c;但凡一个记录不满足#xff0c;v就不满足题意。 从小到大列举v,设置v最大为1e6 设置一个标…冶炼金属
学习了b站Turing_Sheep的思路 一、暴力模拟 思路 b[i] a[i] / v b[1] a[1] / v b[2] a[2] / v .... b[n] a[n] / v 以上列举中v要满足所有的记录但凡一个记录不满足v就不满足题意。 从小到大列举v,设置v最大为1e6 设置一个标志位如果不满足即跳过这个v 如果找到了满足所有记录的v同时也是从小到大排列肯定是最小的v 同理从大到小排列找出最大的v 为什么这里的v取1e6? 因为要枚举所有的v通过N条记录判断是否合法。 v: 1e4*N 1e4*1e4 1e8不超时但是答案会有错误 v: 1e6*N 1e6*1e4 1e10 (会超时但可以保证正确性) #includebits/stdc.h
using namespace std;
const int N 1e410;void solve()
{int n; cin n;vectorinta(n),b(n);for (int i 0; i n; i) cin a[i] b[i];//枚举的转化率v//从小到大枚举 找最小值 for (int i 1; i 1e6; i){bool flag true;//标记当前的v是否合法for (int j 0; j n; j){if (b[j] ! (a[j] / i)){flag false;break; } }if (flag){cout i ;break;}} //从大到小枚举 找最大值for(int i 1e6; i 1; i--){bool flag true;for (int j 0; j n; j){if (b[j] ! (a[j] / i)){flag false;break;}}if (flag){cout i \n;break;}}
}signed main()
{ios::sync_with_stdio(0),cout.tie(0),cin.tie(0);int t;t 1;while(t--)solve();return 0;}
二、二分 思路 将v的排列转化成从1到1e6的一条线而我们要找的就是所有合法v的最大最小值。 对于min左侧的点不包含min;至少存在一组数据满足B[i] A[i] / v 对于min右侧的点不包含min;至少存在一组数据满足B[i] A[i] / v min这个点所对的v中对应的N条数据也是满足B[i] A[i] / v 以上三条即check函数找到我们需要的点分析出该点左右两侧的性质 #includebits/stdc.h
using namespace std;
#define int long long
const int N 1e410;
int a[N],b[N];
int n;
bool check_min(int mid)
{for (int i 0; i n; i)//至少存在一条数据是 if (b[i] a[i] / mid) return false;return true;
}bool check_max(int mid)
{for (int i 0; i n; i)//至少存在一条数据是 if (b[i] a[i] / mid) return false;return true;
}signed main()
{cin n;for (int i 0; i n; i) cin a[i] b[i];// 找最小值 int lmin 1,rmin 1e9;while(lmin rmin){int mid lmin rmin 1;if (check_min(mid)) rmin mid;else lmin mid 1;}// 找最大值int lmax 1, rmax 1e9;while(lmax rmax){int mid lmax rmax 1 1;if(check_max(mid)) lmax mid;else rmax mid - 1;}cout lmin lmax \n;return 0;
}
