佛山按天网站优化服务,wordpress主题科技类,建设银行江苏省分行网站,建设网工程信息一#xff0c;思路#xff1a;
这题我们可以通过二分 w来直接得到答案#xff0c;时间复杂度是nlogn的级别#xff0c;但是这里有个很坑的地方#xff0c;就是假如你用二分做#xff0c;会面临报 long long 的问题#xff0c;但是问题不大#xff0c;直接用 unsigned …一思路
这题我们可以通过二分 w来直接得到答案时间复杂度是nlogn的级别但是这里有个很坑的地方就是假如你用二分做会面临报 long long 的问题但是问题不大直接用 unsigned long long 水过去long long ----1e18,unsigned long long ----1e19。
二代码
#include iostream
#includecstring
#includealgorithm
#includevector
#includecmath
using namespace std;const int N2e510,M1e910;
typedef unsigned long long ll;
ll arr[N],n,c;bool check(ll w){ll sum0;for(int i0;in;i){ll lenarr[i]2*w;sum sum len*len;//主要面临报 long long 的问题就在这个求和的地方
//这里一定要在求的过程中就要判是否符合大于等于 c,
//不能求完再比要不然unsigned long long 都不够if(sumc) return true;}return false;
}void Solved(){cinnc;for(int i0;in;i) cinarr[i];//二分模板ll l1,r 4e9;while(lr){ll mid(lr)1;if(check(mid)) rmid;else lmid1;}coutlendl;
}int main()
{int t;cint;while(t--) {Solved();}return 0;
}
