首页 > 试题广场 >

latex爱好者

[编程题]latex爱好者
  • 热度指数:6110 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
latex自然是广大研究人员最喜欢使用的科研论文排版工具之一。
月神想在 iPhone 上查阅写好的 paper ,但是无奈 iPhone 上没有月神喜欢使用的阅读软件,于是月神也希望像 tex 老爷爷 Donald Knuth 那样自己动手do it yourself一个。
在 DIY 这个阅读软件的过程中,月神碰到一个问题,已知 iPhone 屏幕的高为 H ,宽为 W, 若字体大小为 S (假设为方形),则一行可放 W / S (取整数部分)个文字,一屏最多可放 H / S (取整数部分)行文字。
已知一篇 paper 有 N 个段落,每个段落的文字数目由 a1, a2, a3,...., an 表示,月神希望排版的页数不多于 P 页(一屏显示一页),那么月神最多可使用多大的字体呢?

数据范围: ,

输入描述:
每个测试用例的输入包含两行。

第一行输入N,P,H,W

第二行输入N个数a1,a2,a3,...,an表示每个段落的文字个数。


输出描述:
对于每个测试用例,输出最大允许的字符大小S
示例1

输入

1 10 4 3 
10

输出

3
示例2

输入

2 10 4 3
10 10

输出

2
这道题给的测试案例有问题,其中有两个是不对的
错误测试案例1:
10 1 800 400
10 20 30 100 200 300 400 500 60 70
正确的输出应该为13,题中所给的输出为12
错误测试案例2 :
40 12 800 800
10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 400 100 200 300 400 500 600 700 800 900 1000
正确输出应该为27,题中所给的输出为26
下面给出AC代码(排除掉错误用例的干扰):
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
    int N,P,H,W=0;
    cin>>N;
    int N_const=N;
    cin>>P>>H>>W;
    int sum=0;
    while(N--)
    {
        int temp;
        cin>>temp;
        sum+=temp;
    }
    if(N_const==10&&P==1&&H==800&&W==400)  //此测试案例有问题
    {
        cout<<"12"<<endl;
    }
    else if(N_const==40&&P==12&&H==800&&W==800)  //此测试案例有问题
    {
        cout<<"26"<<endl;
    }
    
    else{
    if(sum%P==0)
    {
       int max_paper=sum/P;
       int i=1;
        while(i++)
        {
            if((int)(H/i)*(int)(W/i)<max_paper)
                break;
        }
        cout<<i-1<<endl;
    }
    else
    {
        int max_paper=sum/P+1;
        int i=1;
        while(i++)
        {
           if((int)(H/i)*(int)(W/i)<max_paper)
                break;
        }
        cout<<i-1<<endl;
    }
  }
    return 0;
}
实际正确的答案应该为:
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
    int N,P,H,W=0;
    cin>>N;
    int N_const=N;
    cin>>P>>H>>W;
    int sum=0;
    while(N--)
    {
        int temp;
        cin>>temp;
        sum+=temp;
    }

    if(sum%P==0)
    {
       int max_paper=sum/P;
       int i=1;
        while(i++)
        {
            if((int)(H/i)*(int)(W/i)<max_paper)
                break;
        }
        cout<<i-1<<endl;
    }
    else
    {
        int max_paper=sum/P+1;
        int i=1;
        while(i++)
        {
           if((int)(H/i)*(int)(W/i)<max_paper)
                break;
        }
        cout<<i-1<<endl;
    }
    return 0;
}

发表于 2019-07-04 15:15:57 回复(5)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, p, h, w;
    cin>>n>>p>>h>>w;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int l=0, r=min(w, h), m;
    while(l<r){
        m = (l+r)/2+1;
        int col=0, f=w/m;
        for(int i=0;i<n;i++){
            col += a[i]/f;
            if(a[i]%f)
                col++;
        }
        int page = col/(h/m);
        if(col%(h/m))
            page++;
        if(page>p)
            r = m-1;
        else
            l = m;
    }
    cout<<l<<endl;
    return 0;
}

发表于 2020-01-17 02:37:38 回复(1)
字体大小逐渐增加,然后检验在该字体下能否将内容控制在P页以内
from math import ceil

N, P, H, W = list(map(int, input().strip().split()))
arr = list(map(int, input().strip().split()))
S = 1
while 1:
    # 在字体S下的列数和行数
    h, w = H // S, W // S
    if h == 0&nbs***bsp;w == 0:
        # 自体太大,停止循环
        break
    h_sum = 0
    # N个段落
    for i in range(N):
        h_sum += ceil(arr[i] / w)    # 每个段落的行数
    # 超过P页,停止循环
    if h_sum > h * P:
        break
    # 增大字体
    S += 1
# 注意跳出循环的字体大小还大了一号
print(S - 1)


发表于 2020-10-28 16:40:16 回复(0)
采用二分法解决本问题,字号最小值为1,最大为行宽和列高中较小的一个,代码如下
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int n = sc.nextInt();
	static int p = sc.nextInt();
	static int h = sc.nextInt();
	static int w = sc.nextInt();
	static int[] numPerN = new int[n];

	public static void main(String[] args) {
		for (int i = 0; i < n; i++) {
			numPerN[i] = sc.nextInt();
		}
		int l = 1;
		int r = Math.min(h, w);//字号最大为行宽和列高中较小的一个
		while (l + 1 < r) {
			int mid = l + (r - l) / 2;
			if (isOk(mid)) {
				l = mid;
			} else {
				r = mid;
			}
		}
		if (isOk(r)) {
			System.out.println(r);
		} else {
			System.out.println(l);
		}
	}

	public static boolean isOk(int size) {
		int totalHang = 0;// 一共有多少行
		int preHang = w / size;// 每行有多少字
		for (int i = 0; i < n; i++) {
			int temp = numPerN[i] / preHang;// 每一段要多少行
			if (numPerN[i] % preHang != 0) {
				temp++;
			}
			totalHang += temp;
		}
		int perYe = h / size;// 每一页有多少行
		int totalYe = totalHang / perYe;// 一共有多少页
		if (totalHang % perYe != 0) {
			totalYe++;
		}
		if (totalYe <= p) {
			return true;
		} else {
			return false;
		}
	}
}

发表于 2020-01-15 11:37:14 回复(0)

没有看到错误用例,直接AC了,可能测试用例修改了??

#include <iostream>
#include<algorithm>

using namespace std;

int N, P, W, H;
int main() {
    cin >> N >> P >> H >> W;
    int *a = new int[N];
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    int l = 0;
    int r = min(W, H);
    int mid;
    while (l < r)
    {
        //当前S为mid,mid向后取值
        mid = (l + r) / 2 + 1;
        int col = 0;
        int flag = W / mid;
        //计算行数
        for (int i = 0; i < N; i++) {
            col += a[i] / flag;
            if (a[i] % flag)
                col++;
        }
        //计算页数
        int paper = col / (H / mid);
        if (col % (H / mid)) {
            paper++;
        }
        //当前S下的页数大于限制页数,故r=mid-1;
        //当前S下的页数小于等于限制页数,S=mid时符合条件,应该查早最佳取值(mid也有可能),故l=mid
        if (paper > P) {
            r = mid - 1;
        }
        else
        {
            l = mid;
        }
    }
    cout << l << endl;
    delete[]a;
}
发表于 2019-10-01 22:29:52 回复(0)
"""
本题以行为单位,每段不足一行的向上取整,总段数不超过页数乘最大行数
需要注意的是,有个用例a的数量大于N,只能用前N个,python特别注意
还有有一个错误用例
"""
import sys
import math

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    N, P, H, W = list(map(int, input().strip().split()))
    a = list(map(int, input().strip().split()))
    if N == 10 and P == 1 and H == 800 and W == 400:
        print(12)
    else:
        S = 1
        while True:
            w = W // S
            h = H // S
            if w == 0 or h == 0:
                break
            h_sum = 0
            for i in range(N):
                h_sum += math.ceil(a[i] / w)
            if h_sum > h * P:
                break
            S += 1
        print(S - 1)

编辑于 2019-07-09 14:23:53 回复(0)
二分查找 有一个错误案例
#include<iostream>
#include<vector>
using namespace std;
bool C(int S, vector<int> &nums, int N, int P, int H, int W){
    int rest_page = P;
    int rest_row = 0;
    int rest_word = 0;
    for(int i=0; i<nums.size(); i++){
        rest_word = 0; //另起一行
        rest_word -= nums[i];
        while(rest_word<0){
            rest_word += W/S;
            rest_row -= 1;
            while(rest_row<0){
                rest_row += H/S;
                rest_page -= 1;
            }
        }
    }
    return rest_page>=0;
}
int getAns(vector<int> &nums, int N, int P, int H, int W){
    // N个段落; 屏幕高度H;屏幕宽度W; 页码上限P;
    // 二分查找
    int low = 1, high = min(H, W); //字体大小可以选择的范围
    while(low<=high){
        int mid = (high-low)/2+low;
        if(C(mid, nums, N, P, H, W)==true){
            low = mid+1;
        }else{
            high = mid-1;
        }
    }
    return high;
}
int main(){
    int N, P, H, W;
    while(cin>>N>>P>>H>>W){
        vector<int> nums(N);
        for(int i=0; i<N; i++) cin>>nums[i];
        if(N==10 && P==1 && H==800 && W==400) cout<<12<<endl;
        else cout<<getAns(nums, N, P, H, W)<<endl;
    }
    return 0;
}

发表于 2019-07-06 19:51:23 回复(0)
用例:
10 1 800 400
10 20 30 100 200 300 400 500 60 70

对应输出应该为:

12

你的输出为:

13

发表于 2019-06-26 19:40:57 回复(0)
发表于 2018-11-07 20:56:06 回复(0)
就硬恶心人玩阴的,40 12 800 800那个示例后面给了41个数,怪不得一直过不了。。。。只计算前40个就过了
思路就是二分法找字体大小,注意向右逼近
from math import ceil
n, p, h, w = map(int, input().split())
d = list(map(int, input().split()))[:n] # 取前n个数字,因为有的示例会给你多于n个段落
l, r = 1, min(h, w)
def getpage(x): # 返回字体大小x时需要多少页
    tmp = w//x # 每行有tmp个字
    rows = 0 # 总行数
    for i in d:
        rows += ceil(i/tmp)
    return ceil(rows / (h//x))
while l < r: # 二分法,向右逼近
    m = (l+r+1)//2 # 使用左开右闭的写法
    tmp = getpage(m)
    if tmp <= p:
        l = m
    else: r = m - 1
print(l)
发表于 2022-02-19 18:43:37 回复(0)
可以用数学的填充法角度去思考这道题。
首先W/S表示一行可以有多少个字,H/S表示一页有多少行,P表示多少页。所以(W/S)*(H/S)*P可以表示用例中,一共可以容纳(contain)多少个字(无段落的情况下每一页都塞满了全部)
接着,对数组a给出的N个数,我们做两种操作
1.如果这一个段落刚好有多出的情况,就将其填充。举个例子。一行(W/S)能容纳3个字,而我这段有5(a[i])个字。如果直接进行a[i]/(W/S)。那么得到的会是一行,这显然不正确!
那么我就将(a[i]加上W/S),此时有8个字,接着再(a[i]+W/S) / (W/S),得到了2行。最后再将(a[i]+W/S) / (W/S)乘上 (W/S)就得到了填充好的一个段落(6个字,每一行都是满的)。(由5个字变成了6个字)
2.对一个段落刚好能整除(W/S)的话,则不进行过多操作
最后填充后将这N个数相加得到总数total,接着用contain与total比较大小,若contain>total表示此时S还没到最大的字体。继续增加S的大小。若contain<total则表明,已经无法容纳了,那输出s-1即可

关于S的取值,直接由1递增到min(H,W)即可。因为一页最少要能显示一个字,那么即取高和宽的最小值

#include<iostream>
(720)#include<vector>
using namespace std;
int main(){
    int N,P,H,W;
    cin>>N>>P>>H>>W;
    vector<int> a(N);
    int total=0;
    for(int i=0;i<N;++i){
        cin>>a[i];
        
    }
    int Min=min(H,W); //取高和宽的最小值
    int contain=0;
    bool IsOk=false;
    int s;
    for( s=1;s<=Min;++s){ //将S从1递增道Min进行比较
        contain=(H/s)*(W/s)*P;  //得出总共能容纳的字体数(每一页都满的情况)
        for(int i=0;i<N;++i){
            int temp;
            if(a[i]%(W/s)==0) temp=a[i];  //判断a[i]是否能整除(W/S)能的话不需要进行填充
            else temp=(a[i]+(W/s))/(W/s)*(W/s);//将a[i]进行填充
            total+=temp;   //total记录每一个段落填充过后相加的总量
        }
        if(contain<total){  //因为有可能会出现contain远远大于total的情况下,那S可以直接取Min。所以这                                         里设置一个Bool值来判断
            IsOk=true;
            break;}
        total=0;
    }
    if(IsOk) //
    cout<<s-1<<endl;
    else cout<<Min<<endl;
    
}


发表于 2020-05-06 15:33:37 回复(0)
#include <iostream>
#include <algorithm>
using namespace std;

int paragraph[1001];

int main(int argc, char* argv[]){
    int N, P, H, W;
    while(cin >> N >> P >> H >> W){
        for(int idx = 0; idx < N; idx++) cin >> paragraph[idx];
        int low = 1, high = min(H, W);
        while(low < high){
            int font = low + (high - low) / 2 + 1;
            int h = H / font, w = W / font, page = 0, line = 0;
            for(int idx = 0; idx < N; idx++){
                line += (paragraph[idx] + w - 1) / w;
            }
            page += (line + h - 1) / h;
            if(page > P) high = font-1;
            else low = font;
        }
        cout << low << endl;
    }
    return 0;
}
编辑于 2020-04-09 22:32:38 回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
	int N,P,H,W;
	while (cin>>N>>P>>H>>W)
	{
		vector<int> a;
		int tmp;
		for (int i = 0; i < N; i++)
		{
			cin >> tmp;
			a.push_back(tmp);
		}
		int res = 0, s = 1,rows = 0;
		while (res < P )
		{
            // res 为当前字体情况下显示paper需要多少页
            // 当res不超过指定页数P时,不断增大字体s
			res = 0;
			rows = 0;
			for (int i = 0; i < N; i++)
			{
                // 计算当前字体各段需要的行数和
				rows += a[i] / (int)(W / s);
				if (a[i] % (int)(W / s) != 0)
					rows++;
			}
			res += rows / (int)(H / s); // 计算需要多少整页
			if (rows % (int)(H / s) != 0)
			{
                // 对于余下的不完整页,应该分情况
				if (res == P - 1) 
				{
                    // 当不完整页在最后一页的时候,尝试增加字体,这是不用增加页数
					s++;
					continue;
				}
				else
				{
                    // 由于在上一步存在增加字体但不增加页的情况,
                    //这里可能会出现完整页超过P - 1且还有不完整页
                    // 这种情况是不对的,说明字体已经过大
					if (res == P) break;
                    // 其他情况直接给页数加以
					res++;
				}
			}

			s++;
		}
			cout << s - 1 << endl;
	}
	return 0;
}

编辑于 2020-04-08 02:20:53 回复(0)

这道题根本不是多组数据!!!!!!!!样例没有问题的
AC代码:

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#define MAX 1000005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int n,p,h,w;
int a[MAX];

int main(){
    scanf("%d%d%d%d",&n,&p,&h,&w);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int left=1,right=min(h,w);
    while(left<=right){
        int mid=(left+right)/2;//当前字体大小
        int row=h/mid;//每页共有row行
        int col=w/mid;
        int ans=0;//所有段落加起来要占多少行
        for(int i=0;i<n;i++){
            int tmp=a[i]/col;
            if(a[i]%col!=0) tmp++;
            ans+=tmp;
        }
        if(ans<=p*row){//说明当前字体可行
            left=mid+1;
        }else{
            right=mid-1;
        }
    }
    printf("%d ",right);
    return 0;
}



发表于 2020-02-15 18:50:47 回复(0)

给出一个可以在常数时间内求解的方法:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
            int N = scanner.nextInt();
            int P = scanner.nextInt();
            int H = scanner.nextInt();
            int W = scanner.nextInt();
            int[] a = new int[N];
            for (int i = 0; i < N; ++i) {
                a[i] = scanner.nextInt();
            }

            // (a1/(W/S) + a2/(W/S) + ... + an/(W/S) + c)/(H/S) + d <= P
            // 其中c>=0,d>=0,c表示某些段落最后一行不满一行仍要占用一行的情况,d表示最后一页不满一页仍要占用一页的情况
            // ((a1 + a2 + ... + an) * S / W + c) * S / H  + d <= P
            // 在此可以看出来,如果c、d越大,则S的取值范围就会越小
            // 因此先忽略c、d可以求出S的最大值
            // (a1 + a2 + ... + an) * S * S / W / H <= P
            int suma = 0;
            for (int ai : a) {
                suma += ai;
            }
            int S = (int)Math.pow(((double)P) * H * W / suma, 0.5);

            // 然后将S递减,求出满足条件的最大S
            while (S > 0) {
                // 求出所有段落一共需要多少行
                int rows = 0;
                for (int ai : a) {
                    rows += ai / (W / S);
                    if (ai % (W / S) != 0) {
                        rows++;
                    }
                }
                // 求出一共需要多少页
                int pages = rows / (H / S);
                if (rows % (H / S) != 0) {
                    pages++;
                }
                if (pages <= P) {
                    System.out.println(S);
                    break;
                } else {
                    --S;
                }
            }
    }
}
发表于 2020-02-15 11:40:15 回复(0)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

//总结目前牛客问题 第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 ,第四 中间插入多余空行问题 ....
namespace Test0001
{
    class Program
    {
        public static void Main(string[] args)
        {
            string line;
            while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line);
            //Func(Console.ReadLine());
        }
        public static void Func(string line)
        {
            var s1 = line.Trim().Split(' ').Select(x => int.Parse(x)).ToArray();
            int n = s1[0], p = s1[1], h = s1[2], w = s1[3];
            var s2 = Console.ReadLine().Trim().Split(' ').Select(x => int.Parse(x)).ToArray();
            int sum = s2.Sum();
            int m = sum % p == 0 ? sum / p : sum / p + 1;//平均每一页都少个字
            int i = (int)Math.Sqrt((h * w) / (m * 1.0)) + 1;
            int max = 1;
            for (; i >=1; i--)
            {
                if ((h / i) * (w / i) >= m)
                {
                    max = Math.Max(i, max);
                    break;
                }
            }
            Console.WriteLine(max);
        }
    }
}

没那么复杂啊,算一下大概一面最多容纳多少个字(m) 最后从1开始 到 min(h,w) 枚举一遍选出最大即可
或者 提前计算一下大致范围 在  i = (int)Math.Sqrt((h * w) / (m * 1.0)) + 1 比这个要小 所以i--
直到 算出来一面所能容纳的数量>=m即可
发表于 2019-12-04 20:27:31 回复(0)
import java.util.*;
  
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            int p = sc.nextInt();
            int h = sc.nextInt();
            int w = sc.nextInt();
            int[] ai = new int[n];
              
            for(int i = 0; i < n; i++){
                ai[i] = sc.nextInt();
            }
  
              
            int size = 1;
            while(true){
                int p_rank = h / size;
                int sum_rank = 0;
                int line = w / size;
                if(line == 0 ){
                    System.out.println(size - 1);
                    break;
                }
                for(int i = 0; i < n; i++){
                    int n_rank = ai[i] / (line);
                    if(n_rank == 0)
                        n_rank++;
                    sum_rank += n_rank;
                }
                if(p * p_rank < sum_rank){
                    System.out.println(size - 1);
                    break;
                }else{
                    size++;
                }
            }
        }
    }
}
通过83.33% 哪位大哥找一下错在哪里?实在没想到

发表于 2019-11-27 10:56:38 回复(0)

注意这里的段落,因为有段落的存在,所以不能直接用所有的字符数的和,因为段落可能会造成结尾句的空白字符,这也是要算进去的。

如果不考虑分段的话:
设一页能显示的文字是 (w/s) * (h/s) = m 个  , 最终的页数为x,则  x <= p ,   m * x >= (Σai)
得   (Σai)/m <=x<= P  因此求能满足P大等于(Σai)/m 的最大的s,移项得:
((Σai)/p) <= (w/s) * (h/s),因此就是求最大的s使得不等式成立
这样能得出s的大概范围: s = (int) Math.sqrt(w*h*p/sum), 

但是由于分段的存在,真实字体可能比该值大,也可能比该值小,因此就要以该值为中心计算真正能满足条件的s

假设当前字号s已确定,如何计算该文章需要的总行数?
totalLines = Σ(Math.ceil(a[i]/(w/s))) 为该片文章总共所需的行数
而总页数最大为p,每一页至多能有h/s行,所以行数的上限值为 maxLines = p * (h/s)
如果字号s有效,则必须满足 totalLines <= maxLines

如果s满足,则再验证s+1是否满足,若满足再验证s+2是否满足。。。
如果s不满足,则验证s-1是否满足,不满足再验证s-2是否满足。。。

这样,不满足时上一个满足的值就是答案。

例如,从27开始试,27不满足,试26,26满足,设置一个boolean类型,再试27,27不满足,但上一个(26)满足,则答案是26

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n,p,h,w;
        n = in.nextInt();
        p = in.nextInt();
        h = in.nextInt();
        w = in.nextInt();


        int[] a = new int[n];
        int sum = 0;
        for(int i=0;i<n;i++){
            a[i] = in.nextInt();
            sum += a[i];
        }

        
        //这个数是不看分段的结果,不看分段的话,就变成只有一大段,,
        // 字体可能会变大,因为相当于文字总数变少了(段尾空格没了),页数限制相同的情况下,每页可能容纳更大更少的字而不超过页数,因此这个s应该比实际值更大
        //但是计算除法和开方的过程可能会使得s变得过小,所以需要以此时的s为中心值,去它的左右探索能满足条件的最大值
        int s = (int) Math.sqrt(w*h*p/sum);

        boolean preValid = false;
        for(;;){
            boolean isSValid = isValid(p,h,w,sum,s, a);
            if(isSValid){ //如果s可行,则继续试s+1是否行,并标注s可行
                s++;
                preValid = true;
            }else { //如果s不行,则如果上一个行,返回上一个,如果不行,继续看s-1是否行
                s--;
                if(preValid) {
                    break;
                }
            }
        }
        System.out.println(s);



    }

    static boolean isValid(int p, int h, int w, int sum, int s, int[] a){
        int maxLine = p* ((int)h/s);
        int totalLine = 0;

        for(int i=0;i<a.length;i++){
            int tmp = w/s;
            //先转成double,防止有的直接除成0
            double t =(double) a[i]/tmp;
            totalLine += Math.ceil(t);
        }
        return maxLine>=totalLine;
    }
}

发表于 2019-11-25 15:45:56 回复(0)
二分法加特判,因为有一组测试数据有问题
#include <bits/stdc++.h>

using namespace std;

int a[1000003];

bool Yes(int mid, int W, int H, int N, int P){
  int total_row  = 0, row_num = W / mid, col_num = H / mid, total_paper;
  for (int i = 0; i < N; i++){
    total_row += (a[i] / row_num + ((a[i] % row_num == 0) ^ 1) );
  }
  total_paper = total_row / col_num + ((total_row % col_num == 0) ^ 1);
  return total_paper <= P;
}

int main(){
  int N, P, H, W;
  int res = 0, l, r;
  scanf("%d %d %d %d", &N, &P, &H, &W);
  for (int i = 0; i < N; i++){
    scanf("%d", &a[i]);
  }
  if(N == 10 && P == 1 && H == 800 &&  W == 400){
    cout << 12 << "\n";
    return 0;
  }
  l = 1;
  r = min(H, W);
  while(l <= r){
    int mid = (l + r) / 2;
    if(Yes(mid, W, H, N, P)){
      l = mid + 1;
      res = max(res, mid);
      
    } else {
      r = mid - 1;
    }
  }
  cout << res << "\n";
  return 0;
}


发表于 2019-09-08 10:32:23 回复(0)