【SNUT集训1】排序 二分 前缀和 差分（6 / 16)

目录

P1094 [NOIP2007 普及组] 纪念品分组 - 排序+贪心+双指针

P1571 眼红的Medusa - 哈希表

P1678 烦恼的高考志愿

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

1、二分法

2、暴力

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

P4552 [Poetize6] IncDec Sequence- 差分思维玄学题

---

P1094 [NOIP2007 普及组] 纪念品分组 - 排序+贪心+双指针

[NOIP2007 普及组] 纪念品分组 - 洛谷

import java.util.*;
 
public class Main
{
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		int target=sc.nextInt();
		int n=sc.nextInt();
		int[] a=new int[n];
		for(int i=0;i
		Arrays.sort(a);
		int res=0;
		int l=0,r=n-1;
		while(l<=r)
		{
			if(a[l]+a[r]<=target) 
			{
				l++;r--;res++;
			}else
			{
				r--;res++;
			}
		}
		System.out.print(res);
	}
}

P1571 眼红的Medusa - 哈希表

眼红的Medusa - 洛谷

import java.util.*;
 
public class Main
{
	public static void main(String[] args)
	{
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt(),m=sc.nextInt();
		int[] a=new int[n];
		Set s=new HashSet<>();
		for(int i=0;i
		for(int i=0;i
		{
			int x=sc.nextInt();
			s.add(x);
		}
		for(int i=0;i
			if(s.contains(a[i])) System.out.print(a[i]+" ");
	}
}

P1678 烦恼的高考志愿

烦恼的高考志愿 - 洛谷

c++版

思路：

朴素思路是：每个人的成绩和每个学校作差 取最小值

但是这样时间复杂度是O(m*n) 会tle

所以我们使用二分优化

• 先将所有学校分数线排序
• 找出学校分数线中最后一个比该人分数小的分数
• 最后取 min（最后一个比该分数小，第一个比该分数大）
• 需要加一个特判：当所有学校的分数都比该分数大时，直接取最小学校分数线-该生成绩

#include 
using namespace std;
 
int main()
{
    int m,n;
    cin>>m>>n;
    int a[100100],b[100100];
    long long res=0;
    
    for(int i=0;i>a[i];
    for(int i=0;i>b[i];
    sort(a,a+m);
    for(int i=0;i
    {
        int l=0,r=m-1;
        while(l
        {
            int mid=(l+r+1)>>1;
            if(a[mid]<=b[i]) l=mid;
            else r=mid-1;
        }
        if(b[i]<=a[l]) res+=a[l]-b[i];
        else res+=min(abs(b[i]-a[l+1]),abs(b[i]-a[l]));
    }
    cout<
}

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
		for(int i=0;i
		Arrays.sort(a);
		for(int i=0;i
		{
			int l=0,r=m-1;
			while(l
			{
				int mid=l+r+1>>1;
				if(a[mid]<=b[i]) l=mid;
				else r=mid-1;
			}
			if(b[i]<=a[l]) res+=a[l]-b[i];
			else
			res+=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 种弹珠，能分给的孩子数为 ⌈gimid⌉" role="presentation">⌈gimid⌉$\lceil \frac{g_i}{mid}\rceil$ ，所以最后孩子数cnt=∑i=1M⌈gimid⌉" role="presentation">cnt=∑Mi=1⌈gimid⌉$cnt=\sum _{i=1}^M\lceil \frac{g_i}{mid}\rceil$
• 如果cnt⩽n" role="presentation">cnt⩽n$cnt⩽n$，则当前的mid太大，分到弹珠的孩子太少，r=mid
• 如果cnt>n" role="presentation">cnt>n$cnt>n$，则当前的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
    {
        cnt+=g[i]/x;
        if(g[i]%x) cnt++; //如果不能均分 还要多分给一个小朋友
    }
    return cnt<=n;
}
 
int main()
{
    cin>>n>>m;
    int maxx=-1;
    for(int i=0;i
    {
        cin>>g[i];
        maxx=max(maxx,g[i]);
    }
    int l=1,r=maxx;
    while(l
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<
    return 0;
}

P4552 [Poetize6] IncDec Sequence- 差分思维玄学题

[Poetize6] IncDec Sequence - 洛谷

思路：

这题可以转化为求出原数列的差分数组b，最后使得 

题目中对数组a的操作，相当于每次能选出  中任意两个数，一个+1，一个-1

• x= b中所有正数之和
• y= b中所有负数之和的绝对值
• 我们需要先正负抵消，这时剩下最后一个数，再单独把这个数消成0
• 所以操作数就是 max(x,y)

• 求方案数 也就是求的可能数
• 完成以上操作后得到的b差分数组就是 
• 要把 x-y 消0，需要  步
• 所以b[1]会有  种方案

#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<<max(zheng,fu)<abs(zheng-fu)+1;
    return 0;
}