java写了超时 栓Q

package text;import java.util.*;public class Text //主类 
{public static void main(String[] args){Scanner sc=new Scanner(System.in);int m=sc.nextInt(),n=sc.nextInt();long res=0;int[] a=new int[m];int[] b=new int[n];for(int i=0;i>1;if(a[mid]<=b[i]) l=mid;else r=mid-1;}if(b[i]<=a[l]) res+=a[l]-b[i];elseres+=Math.min(Math.abs(b[i]-a[l+1]),Math.abs(b[i]-a[l]));}System.out.print(res);}
}

P1024 [NOIP2001 提高组] 一元三次方程求解

[NOIP2001 提高组] 一元三次方程求解 - 洛谷

1、二分法

• 三个答案都在[-100,100]范围内
• 两个根的差的绝对值>=1,保证了每一个大小为1的区间里至多有1个解
• 枚举每个长度为1的区间
• 如果该端点 f(l) 为0，则直接输出该解（注意不能判断f(r)   因为区间内至多1个解）
• 如果该区间左右端点的 f(l) * f(r) <0  说明该区间内存在解
• 此时在这个区间内进行二分查找该解并输出

#include 
using namespace std;double a,b,c,d;double f(double x)
{return a*x*x*x+b*x*x+c*x+d;
}int main()
{int sum=0;double l,r,mid,f1,f2;cin>>a>>b>>c>>d;for(int i=-100;i<100;i++) {l=i;r=i+1;f1=f(l);f2=f(r);if(!f1) //如果端点是零点 直接输出{printf("%.2lf ",l);sum++;}if(f1*f2<0){while(r-l>=0.001){mid=(l+r)/2;if(f(mid)*f(r)<=0) l=mid;else r=mid;}printf("%.2lf ",l);sum++;}if(sum==3) break;}
}

2、暴力

#include 
using namespace std;double a,b,c,d;int main()
{int sum=0;cin>>a>>b>>c>>d;for(double i=-100;i<=100;i+=0.001) {if(fabs(a*i*i*i+b*i*i+c*i+d)<0.0001)printf("%.2lf ",i);if(sum==3) break;}
}

P7585 [COCI2012-2013#1] LJUBOMORA - 二分

[COCI2012-2013#1] LJUBOMORA - 洛谷

思路：

当嫉妒值越大，能分到弹珠的孩子越少，嫉妒值越小，能分到弹珠的孩子越多

得出——嫉妒值有单调性，可以二分

• 首先设嫉妒值为mid，边界 l=1，r=max(g[i]) 最大弹珠数
• 对于第 i 种弹珠，能分给的孩子数为  ，所以最后孩子数
• 如果，则当前的mid太大，分到弹珠的孩子太少，r=mid
• 如果，则当前的mid太小，分到弹珠的孩子太多，l=mid+1

#include 
#define ll long long
using namespace std;const int M=3e5+10;
int g[M],m,n;bool check(int x)
{int cnt=0;for(int i=0;i>n>>m;int maxx=-1;for(int i=0;i>g[i];maxx=max(maxx,g[i]);}int l=1,r=maxx;while(l>1;if(check(mid)) r=mid;else l=mid+1;}cout<

#include 
using namespace std;const int N=1e5+10;
long long a[N],zheng,fu;int main()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=2;i<=n;i++){int x=a[i]-a[i-1];if(x>0) zheng+=x;else fu+=abs(x);}cout<