首页 > 试题广场 >

最小值

[编程题]最小值

热度指数：1395 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛给度度熊出了一个数学题，牛牛给定数字 $\mathit n,m,k$ ，希望度度熊能找到一组非负整数 $\mathit a,b$ 满足 $(n-a)(m-b) \leq k$ 且 $\mathit a+b$ 尽量小。

度度熊把这个问题交给了你，希望你能帮他解决。

输入描述:

一行三个数字

输出描述:

输出最小的。

示例1

输入

12 18 100

输出

说明

当时候, ，此时是最小的解。

算法知识视频讲解

仰望夜空

已知（n-a)(m-b)<=k, n>0, m>0,k>0 a>=0, b>=0;求a+b的最小值。

首先，由于n和m的大小关系不会影响结果，所以我们假设 n<=m

k>=(n-a)(m-b)

=nm-ma-nb+ab

=m(n-a)+b(a-n)

=m(n-a-b)+b(a-n+m)=m(n-(a+b)) + b ((m-n) + a)

>= m(n - (a+b))

所以：a+b >= n - k / m

因此：a+b的最小值是 n - k/m。

#include <iostream>

using namespace std;

#define llong long long

int main() {
llong n,m,k, tmp;
cin>>n>>m>>k;
if(n > m) { tmp = n; n = m; m = tmp; }
cout<<n - k/m<<endl;
}

发表于 2021-12-29 22:08:58 回复(2)

牛客-新蜗牛

思路:

在满足题目的条件下，由m,n中较小的那个独自显小时,a+b最小

证明:

(n−a)(m−b)

=nm−am−bn+ab

=nm−am−bm+bm−bn+ab

=(n−a−b)m+b(m−n+a)

≥(n−a−b)m=[n−(a+b)]m

代码:

    #include <cstdio>
    int main(){
    long long n,m,k;
    scanf("%lld %lld %lld",&n,&m,&k);
    if(n>m){
       long long temp = n;
      n = m;
      m = temp;
      }
      long long sum =0;
      while ((n-sum)*m>k){
      sum++;
      }
      printf("%lld",sum);
    }

发表于 2021-06-15 14:28:32 回复(1)

皮卡丘乒乓

#include <iostream>
using namespace std;
int main()
{
    double n,m,k;
    while(cin>>n>>m>>k)
    {
        int count = 0;
        if(n*m <=k)
            cout<<0<<endl;
        if(n>m)
            swap(n,m);
        while(n--)
        {
            count++;
            if(n*m<=k)
            {
                break;
            }
        }
        
    cout<<count<<endl;
    }
    return 0;
}

发表于 2021-08-07 02:18:52 回复(0)

牛客38459577号

思路:将a,b替换为x,y (n-a)(m-y)<=k,可以转换为线性规划问题 : 目标函数min(z=x+y),约束 m+k/(x-n)<=y(0=<x<n)以及m+k/(x-n)>=y(x>n),不用考虑m+k/(x-n)>=y(x>n)的情况，因为(n,m)一定是m+k/(x-n)>=y(x>n)的最小值点,只用考虑m+k/(x-n)<=y(0=<x<n)的情况

代码:

import java.util.*;

public class Main{
public static void main(String args[]){
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextLong()){
long n = scanner.nextLong();
long m = scanner.nextLong();
long k = scanner.nextLong();

long min = m+n;

long xEnd = n - k/m;
for(long x = 0; x <= xEnd && x < n; x++){
long y = m - k/(n-x);
if(y < 0){
min = Math.min(min, x+0);
continue;
}
min = Math.min(min, x+y);
}
System.out.println(min);
}
}
}

发表于 2021-07-16 23:59:36 回复(0)

三减一

n，m中小值那个二分查找

#include<bits/stdc++.h>
#include <climits>
#include <cstdio>
#include<vector>
#define N 100005
#define mn INT_MIN
#define mx INT_MAX
typedef long long ll;
using namespace std;


int main() {
    ll n,m,k;
    scanf("%lld %lld %lld",&n,&m,&k);
    ll imax=max(n,m);
    ll r=min(n,m);
    ll p=r;
    ll l=1;
    ll ans=INT_MIN;

    while(l<=r)
    {
        ll mid =(l+r)/2;
        if (mid*imax<=k)
        {
            ans=max(mid,ans);
            l=mid+1;
        }else {
            r=mid-1;
        }
    }
    ans=p-ans;
    cout<<ans;
    return 0;
}

发表于 2023-03-24 17:32:11 回复(0)

Lysen-Goto

该题采用贪心算法。尝试让 n*m <= k，要么 n 减一，要么 m 减一，两者的结果都会使得 a+b 加一。所以，我们需要选择 n 和 m 中更小的那一个，让 n*m 下降得更快。以 n=12，m=18 为例，要让 n*m 下降得更快，需要选择更小的 12，因为 11 * 18 < 12 * 17。多次减一后，最后 5 * 18 <= 100 满足题意，此时 a + b = 12 - 5 = 7

综上所述，假设 n 更小，则答案是 n - (k / m)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong(), m = in.nextLong(), k = in.nextLong();
        // 保证 n <= m
        if (n > m) {
            long tmp = n;
            n = m;
            m = tmp;
        }
        // 答案
        System.out.println(n - (k/m));
    }
}

发表于 2023-08-23 10:46:40 回复(0)

Aa234671

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long m = in.nextLong();
        long k = in.nextLong();
        if(n <= m){
            System.out.println(helper(n,m,k));
        }else{
            System.out.println(helper(m,n,k));
        }
    }
 
    public static long helper(long n,long m,long k){
        long num = k / m;
        return n - num;
    }
}

发表于 2023-03-27 22:16:06 回复(0)

Java

热衷技术的小羽

用java求解，非数学方法

思路：

1、 $(n - a)(m - b)<=k$ 当 a 逐渐增大，b值假设固定，则 $(n - a)(m - b)$ 单调递减，则不等式必然可以能够成立。

2、利用这点则 $b\geq m-k/(n-a)$ ，则当 $b= m-k/(n-a)$ （因为长整型）在该工况下a+b取到最小值

3、最后 min（min，a+b）

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long m = in.nextLong();
        long k = in.nextLong();

        long a = 0;
        long b = 0;
        long min = Integer.MAX_VALUE;

        for (; a < n; a++) {
            b = m - k / (n - a);
            if (b >= 0) {
                min = a + b < min ? a + b : min;
            } else {
                b = 0;
                min = a + b < min ? a + b : min;
                break;
            }
        }
        min = a < min ? a : min;

        System.out.print(min);
    }
}

发表于 2023-03-26 21:06:15 回复(0)

kuzma_long

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        long m = in.nextLong();
        long k = in.nextLong();
        long a = 0, b = 0;
        while ((n - a) * (m - b) > k) {
            if (a == n - 1) {
                b++;
            } else if (b == m - 1) {
                a++;
            } else if ((n - a - 1) * (m - b) < (n - a) * (m - b - 1)) {
                a++;
            } else {
                b++;
            }
        }
        System.out.println(a + b);
    }
}

发表于 2023-03-13 18:14:10 回复(0)

quincy_sky

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong();
        long m = scan.nextLong();
        long k = scan.nextLong();
        long count = 0;
        while (n * m > k) {
            long sum = n + m;
            n = Math.min(n, m);
            m = sum - n;
            count++;
            n--;
        }
        System.out.println(count);
    }
}

发表于 2023-03-12 11:38:29 回复(0)

聂海洲

import java.util.*;

public class Main{
public static void main(String[] args) throws Throwable {
Scanner in = new Scanner(System.in);
long n = in.nextLong();
long m = in.nextLong();
long k = in.nextLong();
if (n > m){
long temp = n;
n = m;
m = temp;
}
int res = 0;
while((n - res) * m > k){
res++;
}
System.out.println(res);
}
}

发表于 2022-09-13 12:33:48 回复(0)

牛客516509024号

class Solution {
    public int shuLunText(int n,int m,int k){
        int min=Integer.MAX_VALUE;
        for(int a=0;a<=n;a++){
            for(int b=0;b<=m;b++){
                int s=a+b;
                int level=(n-a)*(m-b);
                if(level<=k){
                    min=min<s?min:s;
                }
            }
        }
        return min;
    }
}
我也不知道对错就这样吧。

发表于 2022-09-12 16:43:57 回复(0)

lf777

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong();
long m = scanner.nextLong();
long k = scanner.nextLong();

long min = Math.min(n,m);
long max = Math.max(n,m);
if(k >= max){
System.out.println(min - k/max);
}
else {
System.out.println(min);
}
}
}

发表于 2022-03-22 14:17:54 回复(0)

牛客141060312号

package main

import (
	"fmt"
	
)

func main() {
	var n,m,k int
	fmt.Scanln(&n,&m,&k)
	if n > m {
		n,m = m,n
	}
	ans := n - k / m
	fmt.Println(ans)
}

发表于 2022-03-21 20:59:09 回复(0)

liuxing997

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long m = sc.nextLong();
        long k = sc.nextLong();
        if(n > m){
             long c = m;
             m = n;
             n = c; 
        }
        System.out.print(n - (k / m));
    }
}

发表于 2021-09-07 10:47:41 回复(0)

小浣熊zzZZ

#include<iostream>
 
using namespace std;
 
int main(){
    long long n=0,m=0,k=0;
    cin>>n>>m>>k;
    cout<<min(m-k/n,n-k/m)<<endl;
    return 0;
}

发表于 2021-08-17 22:45:39 回复(0)