精华内容
下载资源
问答
  • 月度开销

    2020-04-18 20:20:16
    A:月度开销 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB 描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里...

    月度开销

    查看 提交 统计 提问
    总时间限制: 1000ms 内存限制: 65536kB
    描述
    农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。

    约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案,他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天,每天被恰好包含在一个fajo月里。

    约翰的目标是合理安排每个fajo月包含的天数,使得开销最多的fajo月的开销尽可能少。

    输入
    第一行包含两个整数N,M,用单个空格隔开。
    接下来N行,每行包含一个1到10000之间的整数,按顺序给出接下来N天里每天的开销。
    输出
    一个整数,即最大月度开销的最小值。
    样例输入
    7 5
    100
    400
    300
    100
    500
    101
    400
    样例输出
    500
    提示
    若约翰将前两天作为一个月,第三、四两天作为一个月,最后三天每天作为一个月,则最大月度开销为500。其他任何分配方案都会比这个值更大。

    #include <iostream>
    #include <string.h>
    #include <sstream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    int main(){
        int m,n;
        int dailyCost[100001] = {};
        cin >> n >> m;
        for(int i = 0; i < n; ++i){
            cin >> dailyCost[i];
        }
        int s = 0, e = 0;
        int tmpCost[100001] = {};
        memcpy(tmpCost, dailyCost, 4*n);
        sort(tmpCost, tmpCost+n, greater<int>());
        s = tmpCost[0];//这里有个问题,s设定为sum/m程序就跑不出??为什么
        for(int i = 0; i <= n-m; ++i)
            e += tmpCost[i];
        int ans = 0;
        while(s <= e){//跳出迭代的条件
            //即寻找一种分法使得每个月的cost<=mid
            int mid = s + (e - s)/2;
            int cnt = 0;
            for(int i = 0; i < n; ){
                int tmp = 0;
                while(tmp + dailyCost[i] <= mid && i < n)
                    tmp += dailyCost[i++];
                ++cnt;
                if(cnt > m){
                    s = mid+1;
                }
            }
            if(cnt <= m){
                ans = mid;//记录当前答案
                e = mid-1;
            }
        }
        cout << ans << endl;
        return 0;
    }
    
    

    本题存疑,期待后续学习能解决

    展开全文
  • POJ月度开销

    2020-04-12 21:51:23
    #include<bits/stdc++.h> using namespace std;...//把月数视为月度开销的函数 int N,M,spend[100100]; int f(int cost){ int sum=0,fajo=1;//因为每次要等一个月不够放了,才算作一个月,所以最后一个...

    这个题的一个问题就是,我不知道为什么这样“贪心”的求月份是对的。

    #include<bits/stdc++.h>
    using namespace std;
    //N个数,分成M组(只能将相邻的数分成一组),使和最大的那个组,和尽可能的小 
    //把月数视为月度开销的函数
     
    int N,M,spend[100100];
    
    int f(int cost){
        int sum=0,fajo=1;//因为每次要等一个月不够放了,才算作一个月,所以最后一个月算不进去,要初始化为1 
        for(int i=0; i<N; i++){
            if(sum+spend[i]>cost){//如果这个月“不足了” 
                sum=spend[i];//开启下一个月           
                fajo++;
            }
            else sum+=spend[i];
        }
        return fajo;
    }
    
    int main(){
    	scanf("%d%d",&N,&M);
    	int l=0,r=0;
    	for(int i=0;i<N;i++){
    		scanf("%d",&spend[i]);
    		r+=spend[i];
    		l=max(l,spend[i]);
    	} 
    
    	while(l<r){
    		int mid=(l+r)/2;
    		int t=f(mid);
    		if(t<=M) r=mid;
    		else l=mid+1;
    	} 
    	printf("%d",l);
    } 
    
    展开全文
  • 二分,月度开销

    2020-07-09 11:06:38
    009:月度开销 总时间限制: 1000ms 内存限制: 65536kB 描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。 ...

    009:月度开销

    总时间限制: 1000ms 内存限制: 65536kB

    描述
    农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。

    约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案,他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天,每天被恰好包含在一个fajo月里。

    约翰的目标是合理安排每个fajo月包含的天数,使得开销最多的fajo月的开销尽可能少。

    输入
    第一行包含两个整数N,M,用单个空格隔开。
    接下来N行,每行包含一个1到10000之间的整数,按顺序给出接下来N天里每天的开销。

    输出
    一个整数,即最大月度开销的最小值。

    样例输入

    7 5
    100
    400
    300
    100
    500
    101
    400

    样例输出
    500
    提示
    若约翰将前两天作为一个月,第三、四两天作为一个月,最后三天每天作为一个月,则最大月度开销为500。其他任何分配方案都会比这个值更大

    思路:
    题目中的“最大中的最小”是典型的二分查找的问法,本题中“最大”是指,开销尽可能的大,使最大开销划分的月的数量小于等于M,为什么可以取小于,因为用最大的,都能分完,我们可以吧多拆几个月,也可以.最小的是,这个最大满足条件,继续寻找更小的满足条件的.

    #include<cstdio>
    #include<iostream>
    using namespace std;
    
    
    int a[100005];
    int n, m;
    bool isValid(int mid)
    {
    	int cnt = 1;   //如果最后几天的和小于mid那么需要把这几天算一个月,如果加上a[n-1]最后一天大于mid, 则最后一天需要算一个月 
    	int sum = 0;
    	for (int i = 0; i < n;i++)
    	{
    		if (sum + a[i] > mid)
    		{
    			sum = a[i];
    			cnt++;
    			if (cnt > m)    //提前就发现cnt>m 说明mid小了
    				return false;
    		}
    		else
    		{
    			sum += a[i];
    		}
    	}
    	if (cnt > m) return false;
    	return true;
    }
    int main()
    {
    	scanf("%d %d", &n, &m);
    	//L是最大的月花销的左边界,必然要大于等于每天的花销
    	int L = 0;
    	int R = 0;  //R必然小于每开销的总和
    	for (int i = 0; i < n; i++)
    	{
    		scanf("%d",&a[i]);
    		if (a[i]>L) L = a[i];
    		R += a[i];
    	}
    	int res = 0;
    	while (L <= R)
    	{
    		int mid = L + (R - L) / 2;
    		if (isValid(mid)){
    			//这个mid满足最大的,接着寻找更小的
    			res = mid;
    			R = mid - 1;
    		}
    		else L = mid + 1;
    	}
    	printf("%d", res);
    	return 0;
    }
    
    
    展开全文
  • OpenJudge 009:月度开销

    2020-04-11 10:54:37
    009:月度开销 总时间限制: 1000ms 内存限制: 65536kB 描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。 ...

    009:月度开销

    总时间限制: 1000ms 内存限制: 65536kB

    描述
    农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。

    约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案,他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天,每天被恰好包含在一个fajo月里。

    约翰的目标是合理安排每个fajo月包含的天数,使得开销最多的fajo月的开销尽可能少。

    输入
    第一行包含两个整数N,M,用单个空格隔开。
    接下来N行,每行包含一个1到10000之间的整数,按顺序给出接下来N天里每天的开销。

    输出
    一个整数,即最大月度开销的最小值。

    样例输入

    7 5
    100
    400
    300
    100
    500
    101
    400
    

    样例输出

    500
    

    提示
    若约翰将前两天作为一个月,第三、四两天作为一个月,最后三天每天作为一个月,则最大月度开销为500。其他任何分配方案都会比这个值更大。

    思想:
    题目中的“最大中的最小”是典型的二分查找的问法,本题中“最大”是指money尽可能的大,使得按此money划分的周期数小于或等于M;而“最小”就是在前述的money中不断去缩小范围,得到最终结果即可;对于周期数划分可以按照使一个周期的预算最接近给定money,因为划分的cnt在小于M的情况下是可以从已有周期中拿出一些日期来单独成周期且是满足条件的,下面是代码。

    #include<iostream>
    using namespace std;
    
    int check(int money, int* ar, int N) {
    	int cnt = 1, sum = 0;//最后一个sum的1
    	for (int i = 0; i < N; ++i) {
    		if (sum + ar[i] > money) {
    			++cnt;
    			sum = 0;
    		}
    		sum += ar[i];
    	}
    	return cnt;
    }
    
    int solve(int max, int min, int* ar, int M, int N) {
    	int l = min, r = max;
    	int fajo = max;
    	while (l <= r) {
    		int mid = l + (r - l) / 2;
    		int cnt = check(mid, ar, N);
    		/*
    		月份等于M时正好分成M个月份;
    		小于m时,可以将某些月份中的天数拆开组成新月份,满足分成m个月份
    		*/
    		if (cnt <= M) {//最大的最小,在最大里面取最小
    			r = mid - 1;//money过大,缩小
    			fajo = mid;
    		}
    		else
    			l = mid + 1;//money过小,扩大
    	}
    	return fajo;
    }
    
    int main() {
    	int N, M;
    	cin >> N >> M;
    	int* ar = new int[N];
    	int max = 0, min = 0;//查找上界(和),查找下界(单日开支中最大的)
    
    	for (int i = 0; i < N; ++i) {
    		cin >> ar[i];
    		max += ar[i];
    		if (ar[i] > min)
    			min = ar[i];
    	}
    
    	cout << solve(max, min, ar, M, N);
    
    	delete[] ar;
    	return 0;
    }
    
    展开全文
  • openjudge8209_月度开销

    2018-08-05 12:43:23
    openjudge8209_月度开销 时空限制 1000ms/64MB 描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。 ...
  • 3:月度开销 查看 提交 统计 提问 总时间限制:  1000ms   内存限制:  65536kB 描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤...
  • 1243:月度开销 【题目描述】 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。 约翰打算为连续的M (1 ≤ M ≤...
  • noi1-11 06:月度开销

    2019-12-17 22:00:41
    06:月度开销 1000ms 内存限制: 65536kB 描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。约翰打算为...
  • 1243:月度开销 时间限制: 1000 ms 内存限制: 65536 KB【题目描述】 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要...
  • 分派与月度开销是两种经典的二分题型,前者是让最小值尽可能大,后者是使最大值尽可能小。 在求解时,不妨先搭建出二分求解的框架(while循环,left=初值,right=初值,mid=left+(right-left)/2),在对当前mid...
  • 月度开销 描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来N(1 ≤N≤ 100,000) 天里每天需要的开销。 约翰打算为连续的M(1 ≤M≤N) 个财政周期创建预算...
  • 06:月度开销 总时间限制:1000ms内存限制:65536kB描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来N(1 ≤N≤ 100,000) 天里每天需要的开销。 约翰...
  • 1243:月度开销 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 5287 通过数: 1850 【题目描述】 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ ...
  • 4135 月度开销

    2018-06-20 12:53:39
    他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案,他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天,每天被恰好包含在...
  • 【OJ二分06】月度开销

    2017-04-10 23:10:41
    月度开销 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB 描述 农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000...
  • 06:月度开销总时间限制: 1000ms内存限制: 65536kB描述农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。...
  • 算法答疑---06:月度开销 一、总结 一句话总结:n个数分成m组,求组的每个数的和最大的那个组的和的最小值。 算法:二分加贪心 从0--->组的每个数的和最大值 遍历。判断组是否满足,组数小说明值取大了,组数...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 123
精华内容 49
关键字:

月度开销