T1 光
Hikari
好神秘这个题，我觉得我解法够神秘了结果是正解
考虑到这四个数虽然不能二分答案，但是它们的和是能二分答案的
因此对和做二分答案
然后问题变成了 check 怎么写
设和最小的答案为 \((i_1,i_2,i_3,i_4)\)
注意到 \(n\) 只有 \(1500\)，考虑直接 \(n^2\) 枚举前两个数
那么后面俩咋办
注意到可以令 \(i_4=sum-i_1-i_2-i_3\)
把题目里的四个限制移项，移项之后等式左边还剩四组
\(i_3+\lfloor\frac{i_4}{2}\rfloor\ge\) 一坨常数
\(i_4+\lfloor\frac{i_3}{2}\rfloor\ge\) 一坨常数
\(\lfloor\frac{i_3}{2}\rfloor+\lfloor\frac{i_4}{4}\rfloor\ge\) 一坨常数
\(\lfloor\frac{i_4}{2}\rfloor+\lfloor\frac{i_3}{4}\rfloor\ge\) 一坨常数
对于前两组，发现当 \(i_3\) 增大的时候，第一组的值增大，第二组的值减小
说明还是有单调性，继续对 \(i_3\) 二分答案。
后面两组没办法了，因为挂 floor，只能说看起来和前面两组差不多，其实并不是单调的，可以自己试试
所以充分发扬人类智慧，先判前两组限制，前两组过了说明离答案非常近了，所以直接在答案区间左右 \(d\) 的范围内暴力 check 是否合法，合法直接返回，\(d\) 取的 \(8\)，因为分母是 \(4\)
最坏复杂度 \(n^2\log(4n)\log(n+8)\) 不知道为啥这么快
非常卡常，记得常数优化
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d;
//判断 (i1,i2,i3,i4) 是否合法
inline int check(int i1,int i2,int i3,int i4){
if(i3+(i4/2)<c-(i1/2)-(i2/4)){
return 1;//i3 小了
}
if(i4+(i3/2)<d-(i1/4)-(i2/2)){
return -1;//i3 大了
}
if((i3/2)+(i4/4)<a-i1-(i2/2)){
return 0;//接神秘做法
}
if((i4/2)+(i3/4)<b-i2-(i1/2)){
return 0;
}
return 2;//正好是对的
}
//二分答案 i3
inline bool checksum2(int sum,int i1,int i2){
int remain=sum-i1-i2;
int l=0,r=remain;
while(l<=r){
int i3=(l+r)/2;
int i4=remain-i3;
int res=check(i1,i2,i3,i4);
if(res==2) return true;
if(res==1){
l=i3+1;
}
if(res==-1){
r=i3-1;
}
if(res==0){
for(int i=max(0,i3-8);i<=min(remain,i3+8);++i){
//暴力
if(check(i1,i2,i,remain-i)==2){
return true;
}
}
return false;
}
}
return false;
}
//二分答案 sum 的 check() 函数
inline bool checksum(int sum){
for(int i1=0;i1<=sum;++i1){
for(int i2=0;i2<=sum-i1;++i2){
if(i1==114 and i2==22){
}
if(checksum2(sum,i1,i2)){
return true;
}
}
}
return false;
}
signed main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
freopen("light.in","r",stdin);
freopen("light.out","w",stdout);
scanf("%d %d %d %d",&a,&b,&c,&d);
int l=0,r=a+b+c+d,ans=-1;
//二分答案 sum
while(l<=r){
int mid=(l+r)/2;
if(checksum(mid)){
r=mid-1;
ans=mid;
}
else{
l=mid+1;
}
}
cout<<ans<<'\n';
}
/*
50 24 25 12
*/