精华内容
下载资源
问答
  • 对于给定的一个长度为N的正整数数列 A-iA−i ,现要将其分成 M(M≤N)M(M≤N) 段,并要求每段连续,且每段和的最大最小。 关于最大最小: 例如一数列 4 2 4 5 142451 要分成 33 段 将其如下分段: [4...

    题目描述

    对于给定的一个长度为N的正整数数列 A-iA−i ,现要将其分成 M(M≤N)M(M≤N) 段,并要求每段连续,且每段和的最大值最小。

    关于最大值最小:

    例如一数列 4 2 4 5 142451 要分成 33 段

    将其如下分段:

    [4 2][4 5][1][42][45][1]

    第一段和为 66 ,第 22 段和为 99 ,第 33 段和为 11 ,和最大值为 99 。

    将其如下分段:

    [4][2 4][5 1][4][24][51]

    第一段和为 44 ,第 22 段和为 66 ,第 33 段和为 66 ,和最大值为 66 。

    并且无论如何分段,最大值不会小于 66 。

    所以可以得到要将数列 4 2 4 5 142451 要分成 33 段,每段和的最大值最小为 66 。

    输入输出格式

    输入格式:

     

    第 11 行包含两个正整数N,M。

    第 22 行包含 NN 个空格隔开的非负整数 A_iAi​ ,含义如题目所述。

     

    输出格式:

     

    一个正整数,即每段和最大值最小为多少。

     

    输入输出样例

    输入样例#1: 复制

    5 3
    4 2 4 5 1

    输出样例#1: 复制

    6

    说明

    对于 20\%20% 的数据,有 N≤10N≤10 ;

    对于 40\%40% 的数据,有 N≤1000N≤1000 ;

    对于 100\%100% 的数据,有 N≤100000,M≤N, A_iN≤100000,M≤N,Ai​ 之和不超过 10^9109 。

     

    此题思路就是找到所有数中的最大数,和所有数的和,然后二分,一个是左边界,一个右边界

    思考为什么这样做?因为最多的就是分成n组,最少的分成一组;所以就这样找分组;

    然后加上贪心的判断就能成功找到最小值;

    #include <bits/stdc++.h>
    
    typedef long long ll;
    
    using namespace std;
    
    ll n,total,m,a[100005];
    ll r,l,s;
    int check(ll mi)
    {
        total = 0; s = 0;
        for(int i = 1; i <= n; i ++)
        {
            if(s + a[i] <= mi)
            {
                s += a[i];
            }
            else
            {
                s = a[i];
                total++;
            }
        }
        return total >= m;
    }
    int main()
    {
        ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
    
        cin >> n >> m;
    
        for(int i = 1; i <= n; i ++)
        {
            cin >> a[i];
            l = max(a[i],l);
            r += a[i];
        }
    
        while(l <= r)
        {
            ll mid = l + (r - l) / 2;
            if(check(mid))l = mid + 1;
            else r = mid - 1;
        }
    
        cout << l << endl;
        return 0;
    }
    

     

    展开全文
  • 先讲贪心的吧先讲贪心的吧先讲贪心的吧 设a0表示a数组0元素,a1,a2,b0,b1,b2都是如此设a_0表示a数组0元素,a_1,a_2,b_0,b_1,b_2都是如此设a0​表示a数组0元素,a1​,a2​,b0​,b1​,b2​都是如此 只有当a2和b1匹配可以...

    先讲贪心的吧

    a0a0,a1,a2,b0,b1,b2设a_0表示a数组0元素,a_1,a_2,b_0,b_1,b_2都是如此

    a2b12,a1b22只有当a_2和b_1匹配可以加2,只有当a_1和b_2匹配可以减2

    0其他匹配都是0

    ,a2b1思路是,先拿a_2匹配b_1

    原因很简单,只有这一种方法可以产生正贡献

    a2b2....至于你担心也许拿a_2匹配b_2会更优....不存在的

    21+2,b拿2匹配1让答案+2是最好的,因为只影响了b的一个元素

    2,这个元素在后续的影响最多是-2,那也不会让让答案变坏

    a2b2(b)然后拿a_2匹配b_2(优先消耗b大的数字)

    a2b0(b0)然后拿a_2匹配b_0(只能匹配b_0了)

    a0b2(b0,)然后拿a_0匹配b_2(反正和哪个b匹配都是0,不如消掉最大的)

    a0b1然后拿a_0匹配b_1

    a0b0然后拿a_0匹配b_0

    a1,b然后只剩下a_1,必须和b数组的每个元素相匹配了

    我的代码写的比较粗犷,你可以改进一下自己写

    #include <bits/stdc++.h>
    using namespace std;
    #define int long long
    int t,a[5],b[5];
    signed main()
    {
    	cin >> t;
    	while( t-- )
    	{
    		for(int i=0;i<3;i++)	cin >> a[i];
    		for(int j=0;j<3;j++)	cin >> b[j];
    		//0��0�˷�
    		int ans=0;
    		int k=min( a[2],b[1] );//2��1��
    		ans+=k*2;
    		a[2]-=k,b[1]-=k;
    		k=min( a[2],b[2] );
    		a[2]-=k,b[2]-=k;
    		b[0]-=a[2];
    		k=min( a[1],b[1]);//��ģ��1 
    		a[1]-=k,b[1]-=k;
    		k=min( a[1],b[0] );
    		a[1]-=k,b[0]-=k;
    		ans-=a[1]*2;
    		b[2]-=a[1];
    		cout << ans << '\n';
    	} 
    }
    

    还有叫做最小费用最大流的(不会的可以跳过哦)

    24,因为最近在刷网络流24题,发现确实可以写

    a0,1,2,b0,1,2a数组的0,1,2放在左边,b数组的0,1,2放在右边

    ,这构成了一个二分图,每个对应的匹配有对应的权值

    跑最大匹配最大费用即可

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=50009;
    const int inf=1e9;
    int n,m,s,t,a[5],b[5];
    int maxflow,maxcost;
    int dis[maxn],head[maxn<<1],cnt=1,incf[maxn],pre[maxn],vis[maxn];
    struct EDGE{
    	int to,nxt,w,flow;//�ֱ���� 
    }d[maxn<<1];
    void add(int u,int v,int flow,int w)//flow�������,w�����
    {
    	d[++cnt].to=v,d[cnt].flow=flow,d[cnt].w=w,d[cnt].nxt=head[u],head[u]=cnt;
    	d[++cnt].to=u,d[cnt].flow=0,d[cnt].w=-w,d[cnt].nxt=head[v],head[v]=cnt;	
    } 
    bool spfa()
    {
    	queue<int>q;
    	for(int i=0;i<=t;i++)	dis[i]=-inf;
    	memset(vis,0,sizeof(vis));
    	q.push(s);
    	dis[s]=0,vis[s]=1;
    	incf[s] = inf;//��ʼ�������޴�
    	while( !q.empty() )
    	{
    	//	cout << "��֪\n";
    		int u=q.front(); q.pop();
    		vis[u]=0;//����
    		for(int i=head[u];i;i=d[i].nxt)
    		{
    			if( !d[i].flow )	continue;//��������	
    			int v=d[i].to;
    			if( dis[v]<dis[u]+d[i].w )
    			{
    				dis[v]=dis[u]+d[i].w;
    				incf[v] = min(incf[u],d[i].flow);//���µ�ǰ����
    				pre[v]=i;//��¼�������߹�����
    				if( !vis[v] )	vis[v]=1,q.push(v); 
    			}
    		}	
    	} 
    	if( dis[t]==-inf )	return 0;
    	return 1;
    }
    void dinic()
    {
    	while( spfa() )
    	{
    		int x=t;//����ȥ��·��
    		maxflow+=incf[t];
    		maxcost+=dis[t]*incf[t];
    		int i;
    		while(x != s)
    		{
    			i=pre[x];
    			d[i].flow-=incf[t];//��ȥ����
    			d[i^1].flow+=incf[t];//��������
    			x = d[i^1].to;//��Ϊ�ǵ���ȥ,�������÷���ߵ���ȥ 
    		} 
    	}
    }
    int main()
    {
    	int T; cin >> T;
    	while( T-- )
    	{
    		for(int i=0;i<=100;i++)	head[i]=0;
    		cnt=1,maxcost=0;
    		s=0,t=7;
    		for(int i=1;i<=3;i++)	cin >> a[i];
    		for(int i=1;i<=3;i++)	cin >> b[i];
    		for(int i=1;i<=3;i++)
    		{
    			add(s,i,a[i],0);
    			add(i+3,t,b[i],0);
    		}
    		for(int i=4;i<=6;i++)	add(1,i,a[1],0);
    		add(2,4,a[2],0);
    		add(2,5,a[2],0);
    		add(2,6,a[2],-2);
    		add(3,4,a[3],0);
    		add(3,5,a[3],2);
    		add(3,6,a[3],0);
    		dinic();
    		cout << maxcost << '\n';
    	}
    }
    
    展开全文
  • 最小差值Ⅱ--贪心

    2020-07-21 21:32:40
    到 A[i] 中。 在此过程之后,我们得到一些数组 B。 返回 B 的最大值和 B 的最小值之间可能存在的最小差值。 示例 1: 输入:A = [1], K = 0 输出:0 解释:B = [1] 示例 2: 输入:A = ...

    LeetCode

    最小差值 Ⅱ

    给定一个整数数组 A,对于每个整数 A[i],我们可以选择 x = -K 或是 x = K,并将 x 加到 A[i] 中。

    在此过程之后,我们得到一些数组 B。

    返回 B 的最大值和 B 的最小值之间可能存在的最小差值。

    示例 1:

    输入:A = [1], K = 0
    输出:0
    解释:B = [1]
    

    示例 2:

    输入:A = [0,10], K = 2
    输出:6
    解释:B = [2,8]
    

    示例 3:

    输入:A = [1,3,6], K = 3
    输出:3
    解释:B = [4,6,3]
    

    解法1:线性搜索

    解题思路:我们可以在数组中的任一元素加K或减K,然后得到一个新的数组,要得到所有可能的数组的最小差值(最大值减去最小值),我们只要将数组排序,然后从0开始遍历,当遍历到A[i]时,将左边即0->i全部加上K,将i+1->n-1全部减去K,这样,最大的数可能是A[i]+K或者A[n-1]-K,最小的数可能是A[0]+K,或者是A[i+1]-K,因此,我们只要找到最大和最小,求出差值就可以了

    完整代码:

    class Solution {
        public int smallestRangeII(int[] A, int K) {
            int N = A.length;
            Arrays.sort(A);
            int ans = A[N-1] - A[0];
    
            for (int i = 0; i < A.length - 1; ++i) {
                int a = A[i], b = A[i+1];
                int high = Math.max(A[N-1] - K, a + K);
                int low = Math.min(A[0] + K, b - K);
                ans = Math.min(ans, high - low);
            }
            return ans;
        }
    }
    

    题目以及解法来源于

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/smallest-range-ii
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    展开全文
  • 910. 最小差值 II 题目来源:力扣(LeetCode) ...解题思路: 这道题的题意是A数组中的每个元素要么K、要么减K,只能进行其中的一个操作...1、x、y都K与都减K的结果与原数组A中的最大最小元素的差值一样。算一种情况。

    910. 最小差值 II

    题目来源:力扣(LeetCode)
    https://leetcode-cn.com/problems/smallest-range-ii/

    解题思路:

    这道题的题意是A数组中的每个元素要么加K、要么减K,只能进行其中的一个操作。在每个元素操作完后就构成一个新的数组B,要求使B中数组元素的最大值与最小值的差值最小。

    对于这道题,我们先来考虑所有情况:假设两个数x、y,且x<y。

    1、x、y都加K与都减K的结果与原数组A中的最大最小元素的差值一样。算一种情况。 即 (y+k)-(x+k)=y-k 或 (y-k)-(x-k)=y-k 。
    2、y加k、x减k。即(y+k)-(x-k)=y-x+2k。
    3、y减k、x加k。即(y-k)-(x+k)=y-x-2k。

    若k>0,我们只需要考虑第三种情况。只有第三种情况下的值最小(可能与第一种一样)。

    那么我们可以想,先将原数组进行从小到大排序,这样得到原数组中最小元素A[0]与最大元素A[n-1]。此时最大与最小元素差值为A[n-1]-A[0]。此时包括第一种情况。

    对于第二种情况,当大的元素加K而小的元素减K,最终会导致新数组元数中的最大值与最小值之差比原数组的结果大,故不需要考虑。

    最终只有第三种情况需要考虑,即大的元素减K,小的元素加K,这种情况才可能出现比原数组的结果更小的结果。注意:差值最大不会大于A[n-1]-A[0],只能比A[n-1]-A[0]小。

    现在如何根据第三种情况使结果最小。首先根据排序后的数组,我们得到第一种情况的解;现在再遍历排序后的数组的相邻两位数,如A[i]、A[i+1],有A[i]<A[i+1]。A[i]+k一定会大于A[0]+k,只需要考虑A[i]+k与A[n-1]-k的大小,要在这两者中选一个最大的;A[i+1]-k一定小于A[n-1]-k,只需要考虑A[i+1]-k与A[0]+k的大小,要在这两者中选一个最小的。这样就得到一个新数组中的结果。

    代码:

    public int smallestRangeII(int[] A, int K) {
        // 先对数组进行排序
        Arrays.sort(A);
        int n = A.length;  // 数组长度
        // 排序后,A[0]为数组最小值,A[n-1]为数组最大值。求得原数组中最大与最小值之差
        int res = A[n-1]-A[0];
        // 遍历数组中的每相邻的两个元素
        for (int i = 0; i < n-1; i++) {
            int max = Math.max(A[n-1]-K,A[i]+K);
            int min = Math.min(A[0]+K,A[i+1]-K);
            int error = max - min;
            // 取小的结果。
            res = Math.min(res,error);
        }
        return res;
    }
    
    展开全文
  • 返回 B 的最大值和 B 的最小值之间可能存在的最小差值。 示例 1: 输入:A = [1], K = 0 输出:0 解释:B = [1] 示例 2: 输入:A = [0,10], K = 2 输出:6 解释:B = [2,8] 示例 3: 输入:A = [1,3,6], K = 3 ...
  • 返回 B 的最大值和 B 的最小值之间可能存在的最小差值。 示例 1: 输入:A = [1], K = 0 输出:0 解释:B = [1] 代码 class Solution { public int smallestRangeII(int[] A, int K) { for(int c=0;c<A.length...
  • 贪心算法----最小差值

    2019-04-07 18:09:43
    没做出来,看了老哥们的题解才恍然大悟 ...返回 B 的最大值和 B 的最小值之间可能存在的最小差值。 示例 1: 输入:A = [1], K = 0 输出:0 解释:B = [1] 示例 2: 输入:A = [0,10], K = 2 输出:...
  • 51nod1378 树形dp加贪心

    2019-08-30 14:39:58
    夹克老爷逢三抽一之后,由于采用了新师爷的策略,乡民们叫苦不堪,开始组织起来暴力抗租。 夹克老爷很愤怒,他决定派家丁常驻村中进行镇压。...夹克老爷一贯奉行最小成本最大利润的原则,请问要实现对全部村庄的...
  • 思路:这里就要看往那边贪心了,因为解决的是最大最小化,最小值最大化。也就是说当满足大于等于c时,l=mid+1这样的二分得到的就是在所有满足条件函数下的最右端. #include<iostream> #include<...
  • 题意 两个人玩n轮游戏,每次两个人各取一个数,并且已知对手的取数顺序,如果你取的数比他大就算赢一轮,求能赢最多轮次的取法,如果有多种...有经验的选手就知道,像保证什么最小的情况下求最大以及什么最大的情...
  • 试设计一个算法,计算出将n堆石子合并成一堆的最大总费用和最小总费用。 对于给定n堆石子,计算合并成一堆的最大总费用和最小总费用。 Input 输入数据的第1 行有2 个正整数n和k(n≤100000,k≤1000...
  • 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。 说明: 假设你总是可以到达数组的最后一个位置。 算法思路ac代码 每次选择的优先级...
  • 题目大意你有一个n个点m条边的森林,编号从0开始,边有边权,你现在要添加若干边...解题思路求出每一个连通块的半径,答案及第一大第二大+L和第二大第三大+2L取最大。code#include #include #include #include #
  • 这题比较巧妙地去猜答案,二分,重点是怎么求m段的连续和是否满足,这里用了一个贪心, 不大于x,就一直把线往后移,大于的话就一条线。 #include #include #include #include #include #include #include #...
  • 题意是说,找出使点1到点n的连通的所有路径上权值最小边的最大值,即有路能连通所有点,这路上的最大权值为x,找出最小的x; 这是最小生成树的模板题; 可以按照最小生成树kruskal的贪心思想,依次寻找图中从小到大的...
  • 1、极差的贪心算法实现,数列极差问题描述:给定,n,个正整数数列,进行如下操作:每次删去两个数,a,和,b,添,一个数,a*b+1,直到只剩一个数,N,在所,有这样的,N,中,有一个最大,Max,和最小,Min,M=Max-Min,是极差。...
  • 先将所到湖的个数枚举,直接将走路时间减去,这样就可以贪心了,在枚举所选的湖个数的时候,那个湖鱼多久去那个湖,然后分别比较枚举的每种情况所抓鱼的数量,这样得出最大值!!!! 令我纠结好几个点的问题还不知...
  • hdu 6000 Wash 贪心

    2017-01-12 20:20:21
    看了这篇题解:见这里,思想就是最小洗完时间加最大脱水时间取大,仔细想想这个贪心确实是正确的啊,虽然我不能证明它,但是直观感觉这样得到的答案确实是最优的。然后就按照这个思想贪心做就好了。代
  • POJ 3614 (贪心)

    2019-04-02 16:51:00
    如果牛最小承受小于防晒霜的,让牛的最大防晒进队。然后判断队列里面牛的最大承受大于防晒霜,就答案1 #include<cstdio> #include<queue> #include<algorithm> using namespace s...
  • CodeForces 520D 又见贪心

    2019-10-03 08:03:13
    //贪心的做法比较明显:取出方格中的数从左往右排列形成一个 m 进制的数,前者想要数最大,则每次取符合条件的最大的数,后者想要数最小,则每次取符合条件的最小的数。 //做法也比较暴力:在整个剩余的数形成的集合...
  • C. RationalLee(贪心

    2020-06-24 15:00:06
    中间那些是什么并不关心,所以我们从拿的最多的那个人开始,因为当前剩下的数中,最小最大的那两个数肯定是要被计算的,所以我们把这两个数给到这个人,中间的话我们考虑贪心,把剩下尽可能小
  • HDU 4968 (贪心)

    2016-06-27 09:29:20
    最大的GPA可以这么构造,先使得每一门都是60分,然后每次多余的分数给一门课到85 。最小的GPA也类似,先使得每一门是69,然后多余的分数每次给一门到100 。#include using namespace std; #define maxn 111int ...
  • 贪心」耍杂技的牛

    2019-09-29 14:39:00
    给你\(n\)头牛,每头牛有一个重量 \(w_i\) 和 强壮程度 \(s_i\),现在要把牛叠起来,每头牛有一个风险值,这个风险值当前这头牛头上的所有牛重量起来减去当前这头牛的强壮程度,要使这个值最大最小 题目题解 ...
  • 贪心法之主持人的烦恼 问题: 思路: 若要达到组数最大,则对每个元素,应选择最有可能与其组成一组的元素与其组合。对输入排序,从数组的第一个元素起,最有可能与其组成一组的元素即为其后继元素(因为其后继...
  • 题意:给一个字符串和一个数m,让你从中取出一串非连续子串。使原串中每m个元素,至少含一个子串中...思路:贪心,先找出满足条件的子串最大字母的最小可能,然后将原串中小于最大字母的元素到子串中,最后删除尽可
  • 投票为11结果的人一定会被全选上,而从投01和投10的人中选最小的人数,11和01和10中最小起来就是最小票选人数。 然后再在01或10中剩下的和00中取11人数的人数求出来的价值就是答案。 当然是先进行排序处理。 ...
  • 最小支配集

    2019-08-01 18:44:32
    最小支配集,最大独立集,最小点覆盖参考博客...最后反向贪心选择点,如果这个点没有被标记,我们就将他父亲进点集里面标记这个点 ,父节点,父节点的父节点(至于为什么反...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 193
精华内容 77
关键字:

最大加最小贪心