精华内容
下载资源
问答
  • 代码: #include <iostream> using namespace std; int max_ = 0; int sum = 0; int sum_temp = 0; int count_ = 0; //n is the length of arr,m is the number of your split. int func(int* arr,int n,......

    在这里插入图片描述
    代码:

    #include <iostream>
    using namespace std;
    int max_ = 0;
    int sum = 0;
    int sum_temp = 0;
    int count_ = 0;
    //n is the length of arr,m is the number of your split.
    int func(int* arr,int n,int m)
    {
        for(int i=0;i<n;++i)//this loop is to get the max and sum,is also the floor and ceil of next loop.
        {
            if(arr[i]>max_)
            {
                max_ = arr[i];
            }
            sum+=arr[i];
        }
        for(int j=max_;j<=sum;j++)//between the max and sum,we make a loop to get the smallest number that meets the condition.
        {
            for(int k=0;k<n;k++)
            {
                sum_temp += arr[k];
                if (sum_temp > j)//when the current sum of this part is bigger than j,we split.
                {
                    count_++;
                    sum_temp = arr[k];
                }
            }
            if(count_ < m)//when count_ < m,we say this j meets the condition.Because since you can split it by count_ times,
                // and count_<=m-1,so you must be able to split it by m-1 times,and of course get m parts, the sum of each part <=j.
            {
                return j;
            }
    
            else
            {
                count_ = 0;// if there is no count_<m,we set the count_ 0.and j+=1,begin next loop,until we get the smallest j
                //that meets the condition.
                sum_temp = 0;
            }
        }
        return sum;//if all cases can't meet the condition,so the sum of arr will be returned.
    }
    int main(){
        int array_test[5] = {1,4,2,3,5};
        cout<<func(array_test,5,3);
        return 0;
    }
    

    参考:
    https://blog.csdn.net/seniusen/article/details/80539553

    展开全文
  • 题目: 给 n 个正整数 a_1,…,a_n, ...问所有分割方案中分割分数的最小值是多少? 输入描述: 第一行依次给出正整数 n, m。 第二行依次给出n 个正整数 a1,...,ana1,...,ana_1,...,a_n。 示例: 输入 5 3 ...

    题目:

    给 n 个正整数 a_1,…,a_n, 将 n 个数顺序排成一列后分割成 m 段,每一段的分数被记为这段内所有数的和,该次分割的分数被记为 m 段分数的最大值。问所有分割方案中分割分数的最小值是多少?

    • 输入描述:
      第一行依次给出正整数 n, m。
      第二行依次给出n 个正整数 a1,...,an

    • 示例:

      输入
      5 3
      1 4 2 3 5
      输出
      5

    • 说明
      分割成 1 4 | 2 3 | 5 的时候三段的分数都为 5,得到分割分数的最小值。

    • 备注:
      对于所有的数据,有 m <= n <= 100000,0 <= ai <= 2^39。

    • 思路

      1. 将 n 个数划分为 n 段,分割分数即为 n 个正整数的最大值;
      2. 将 n 个数划分为 1 段,分割分数即为 n 个正整数的和;
      3. 若分为 m 段,则分割分数一定介于最大值与和之间。因此采用二分查找,每次取一个值对序列进行划分,若能划分出
        m 段,使得每段的和都小于这个数值,则满足划分,反之不满足,直至找到一个最小的满足划分的值为止。
    • 代码实现如下:

    #include <iostream>
    using namespace std;
    
    int Judge(int data[], int sum, int m, int n);
    int Binary_Search(int data[], int left, int right, int m, int n);
    
    
    int main()
    {
        int n = 0, m = 0;
        cin >> n >> m;
    
        int data[n];
        int max_num = 0;
        int sum = 0;
    
        int i = 0;
    
        for(i = 0; i < n ; i++)
        {
            cin >> data[i];
            if (data[i] > max_num)
            {
                max_num = data[i];
            }
            sum += data[i];
        }
    
        cout << Binary_Search(data, max_num, sum, m, n);
    
        return 0;
    }
    
    int Binary_Search(int data[], int left, int right, int m, int n)
    {
        int mid = 0;
    
        while (left < right)
        {
            mid = left + (right - left) / 2;
            if (Judge(data, mid, m, n)) //满足划分,继续向左寻找
            {
                right = mid;//不减是因为无法确保减一之后的数是否满足划分
            }
            else    //不满足划分,继续向右寻找
            {
                left = mid + 1;
            }
        }
    
        return left;
    }
    
    int Judge(int data[], int mid, int m, int n)
    {
        int cnt = 0;
        int sum = 0;
    
        for (int i = 0; i < n; i++)
        {
            if (sum + data[i] > mid) //累加和大于 mid,进行一次划分
            {
                sum = data[i];
                cnt++;
                if (cnt > m - 1)    //划分次数大于 m-1,不满足划分
                {
                    return 0;
                }
            }
            else
            {
                sum += data[i];
            }
        }
    
        return 1;
    }

    个人见解,如有错误,欢迎指正与交流!

    获取更多精彩,请关注「seniusen」!
    这里写图片描述

    展开全文
  • 此题目为 今日头条 2018 AI Camp 5 月 26 日在线笔试编程题第二道——最小分割分数。 class Solution { public: // 若分割数组的最大值为 value,判断能否进行划分 bool cansplit(vector<int>& n...
        

    1. 题目

    2. 解答

    此题目为 今日头条 2018 AI Camp 5 月 26 日在线笔试编程题第二道——最小分割分数

    
    class Solution {
    public:
        
        // 若分割数组的最大值为 value,判断能否进行划分
        bool cansplit(vector<int>& nums, int value, int m)
        {  
            int len = nums.size();
            int i = 0;
            int sum = 0;
            int split_count = 0; // 分割次数
            
            // 依次往后求和,若和小于等于 value,则继续加;
            // 若和大于 value,则分割次数加 1,从当前位置开始将和清零,重新开始
            for (i = 0; i < len; i++)
            {
                if (sum + nums[i] <= value)
                {
                    sum += nums[i];
                }
                else
                {
                    split_count++;
                    sum = nums[i];
                }
                
                if (split_count == m)  // 分割次数超出 m, 不满足划分
                {
                    return false;
                }
            }
            
            return true;           
        }
        
        int splitArray(vector<int>& nums, int m) {
            
            int len = nums.size();
            int i = 0;    
            // 分割数组的最大值介于数组的最大元素和数组所有元素的和之间
            int max = nums[0];
            int sum = 0;
            for (i = 0; i < len; i++)
            {
                if (nums[i] > max)
                {
                    max = nums[i];
                }
                sum += nums[i];
            }
            
            int left = max;
            int right = sum;
            int mid = 0;
            while(left < right)
            {
                mid = left + (right - left) / 2;
                
                if (cansplit(nums, mid, m)) // 能划分,继续找有没有更小的值
                {
                    right = mid; //不减是因为无法确保减一之后的数是否满足划分
                } 
                else // 不能划分,增大数值继续寻找
                {
                    left = mid + 1;
                }
            }
            
            return left; 
            // 最终 left = right 结束,left 值就是所求
            
        }
    };
    

    获取更多精彩,请关注「seniusen」!

    展开全文
  • 任意两个点之间最多有一条,不存在连接自身的),每条光缆有一定的价值,网络中1为起点,n为终点,现在要求找出一些光缆能分割开1到n,使它们不能相互通信,并且要求花费的和除以光缆数的值最小。输出选择的光缆的...

    zoj2676:题目链接

    题目大意:有一个n个点的网络,其中有m条光缆(所有的点都被连接,任意两个点之间最多有一条,不存在连接自身的),每条光缆有一定的价值,网络中1为起点,n为终点,现在要求找出一些光缆能分割开1到n,使它们不能相互通信,并且要求花费的和除以光缆数的值最小。输出选择的光缆的编号。

    从问题中可以看出一定是0-1分数规划的题目,假设选出光缆的集合M,M为原图的一个割,光缆si∈M,价值为ci,数量k = 1 ,可以推出g(x) = min( ∑c - x*∑k ),因为si是割中的边,将边的值转化为ci-x*k,那么g(x)为原图的最小割。这样就得到了单调关系,对于x的值进行二分,求最小割。求得当g(x)为0的时候的x,也就是花费的和除以光缆数的值最小。

    求到x值以后,从1点进行搜索,找出所有能走到的点。如果一条边的两个点,一个被遍历到,一个没有被遍历到,那么这条边为一条割边。

    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <queue>
    #include <vector>
    #include <algorithm>
    using namespace std ;
    #define eqs 1e-9
    #define INF 0x3f3f3f3f
    struct node{
        int u , v ;
        double w ;
        int next , id ;
    }edge[2100] , p[600] ;
    int head[110] , cnt , id[110][110] ;
    int n , m , l[110] , vis[110] , flag[600] , num ;
    double sum[110][110] ;
    queue <int> que ;
    vector <int> vec ;
    void add(int u,int v,double w,int id) {
        edge[cnt].u = u ; edge[cnt].v = v ; edge[cnt].w = w ;
        edge[cnt].next = head[u] ; edge[cnt].id = id ; head[u] = cnt++ ;
        edge[cnt].u = v ; edge[cnt].v = u ; edge[cnt].w = 0 ;
        edge[cnt].next = head[v] ; edge[cnt].id = id ; head[v] = cnt++ ;
    }
    int bfs(int s,int t) {
        int u , v , i ;
        memset(l,-1,sizeof(l)) ;
        while( !que.empty() ) que.pop() ;
        que.push(s) ;
        l[s] = 0 ;
        while( !que.empty() ) {
            u = que.front() ;
            que.pop() ;
            for(i = head[u] ; i != -1 ; i =  edge[i].next) {
                v = edge[i].v ;
                if( l[v] == -1 && edge[i].w >= eqs ) {
                    l[v] = l[u] + 1 ;
                    que.push(v) ;
                }
            }
        }
        if( l[t] > 0 ) return 1 ;
        return 0 ;
    }
    double dfs(int u,int t,double min1) {
        if( u == t ) return min1 ;
        int v , i ;
        double temp , ans = 0 ;
        for(i = head[u] ; i != -1 ; i = edge[i].next) {
            v = edge[i].v ;
            if( l[v] == l[u]+1 && edge[i].w >= eqs && ( temp = dfs(v,t,min(min1,edge[i].w) ) ) ) {
                edge[i].w -= temp ;
                edge[i^1].w += temp ;
                ans += temp ;
                min1 -= temp ;
                if( min1 < eqs ) break ;
            }
        }
        if( ans >= eqs ) return ans ;
        l[u] = -1 ;
        return 0 ;
    }
    double solve(double mid) {
        int i , j ;
        double ans = 0 , temp ;
        memset(head,-1,sizeof(head)) ;
        memset(flag,0,sizeof(flag)) ;
        cnt = num = 0 ;
        for(i = 0 ; i < m ; i++) {
            if( p[i].w - mid < 0 ){
                flag[i] = 1 ;
                num++ ;
                ans += p[i].w-mid ;
                continue ;
            }
            add(p[i].u,p[i].v,p[i].w-mid,i) ;
            add(p[i].v,p[i].u,p[i].w-mid,i) ;
        }
        while( bfs(1,n) ) {
            while( (temp = dfs(1,n,INF) ) >= eqs )
                ans += temp ;
        }
        return ans ;
    }
    void f_dfs(int u) {
        int i , v ;
        for(i = head[u] ; i != -1 ; i = edge[i].next) {
            v = edge[i].v ;
            if( vis[v] || edge[i].w < eqs ) continue ;
            vis[v] = 1 ;
            f_dfs(v) ;
        }
    }
    void f() {
        int i , u , v ;
        memset(vis,0,sizeof(vis)) ;
        vis[1] = 1 ;
        f_dfs(1) ;
        for(i = 0 ; i < cnt ; i += 2) {
            u = edge[i].u ; v = edge[i].v ;
            if( vis[u] && !vis[v] && edge[i].w < eqs && !flag[ id[u][v] ] ) {
                flag[ id[u][v] ] = 1 ;
                num++ ;
            }
        }
    }
    int main() {
        int i , j ;
        int u , v ;
        double w , low , mid , high , temp ;
        while( scanf("%d %d", &n, &m) != EOF ) {
            low = mid = high = 0.0 ;
            memset(head,-1,sizeof(head)) ;
            cnt = 0 ;
            for(i = 0 ; i < m ; i++) {
                scanf("%d %d %lf", &p[i].u, &p[i].v, &p[i].w) ;
                id[ p[i].u ][ p[i].v ] = id[ p[i].v ][ p[i].u ] = i ;
                high += p[i].w ;
            }
            while( high - low >= eqs ) {
                mid = (high + low) / 2.0 ;
                temp = solve(mid) ;
                if( fabs(temp) < eqs ) break ;
                if( temp < 0 )
                    high = mid ;
                else
                    low = mid ;
            }
            f() ;
            printf("%d\n", num) ;
            for(i = 0 ; i < m && num ; i++) {
                if( !flag[i] ) continue ;
                num-- ;
                if( num ) printf("%d ", i+1) ;
                else printf("%d\n", i+1) ;
            }
            printf("\n") ;
        }
        return 0 ;
    }

    展开全文
  • 对于每个问题,都有一个难度分数di,它是一个正数。 Jagger希望学生从最简单到最难解决问题,因此这些问题按照其难度分数的升序排列。难度差距定义为任意两个连续问题之间的难度分数之差。 贾格尔要最小化最大难度...
  • LC-592 分数加减

    2019-01-07 15:32:00
    对字符串分割出每一个分数(包含符号),然后用两个vector来分别存分子和分母。 解析字符串后,对所有分母找他们的最小公倍数,然后对分子进行相应的加倍后加减,算出总和。 最后计算分子总和与分母最小公倍数的...
  • 问所有分割方案中分割分数的最小值是多少? 思路 二分搜索. 首先定义一个函数 check, 返回布尔型, 用来检查能不能用一个数 x 来将数组分割成 m 份, 使得每份的和不大于 x. 显然如果 x 足够大, 是可以的, 而 x 如...
  • 任意两个点之间最多有一条,不存在连接自身的),每条光缆有一定的价值,网络中1为起点,n为终点,现在要求找出一些光缆能分割开1到n,使它们不能相互通信,并且要求花费的和除以光缆数的值最小。输出选择的光缆的...
  • 棋盘分割可以说是DP问题的经典,在刘汝佳老师的《算法艺术与信息学竞赛》上给出的一道例题,分析公式,要使最后的西格玛最小只要使每个方格的分数的平方和最小就行了,因为平均值使一个定值; 思路: 1,先化简均...
  • 输出最小分数 输入:aaadbccb 输出:2 aaa、d、bccb需要两刀分割成3个回文子串。分析d[i]表示input.substring(0,i)子串的最少回文子串个数 状态转移:d[i]=min(d[j]+1|input.substring(j,i)是回文) 刀数 = ...
  • 小学时候就学过,分数的加减法是先求两个分母的最小公倍数,然后分子分别乘以最小公倍数与自己分母的商,相加后约分即可。所以,本题只要按+,-两个符号分割输入字符串,就可以得到所有的分数列表,做加减操作即可。...
  • CART树

    2018-07-06 17:42:00
    它采用一种二分递归分割的技术,分割方法采用基于最小距离的基尼指数估计函数,将当前的样本集分为两个子样本集,使得生成的的每个非叶子节点都有两个分支。因此,CART算法生成的决策树是结构简洁的二叉树。 叶子...
  • 银行考题,将阿拉伯数字转换成大写的汉字模式 例如    123456789.01 -&gt; 壹亿贰千叁百肆十伍万陆千柒百捌十玖元零壹分 ...3.按照“.” 分割 分别处理整数分数 按照“.” 分割 请注意 http://...
  • APIO2015简要题解

    2017-02-17 23:32:00
    最近老师把apio的题目拿出来了,然后由于我实在是菜,分数还没三位数......  ----------------我是分割线 1.巴厘岛的雕塑 N个数,分成连续的A-B个组,让每个组的和或起来最小,求最小值。 对于Task1 n<=100 ...
  • 黄金点

    2019-09-26 22:51:50
    对所有玩家输入的数做如下处理:先求和再平均,将平均数乘以黄金分割数0.618得出黄金值,用黄金值分别减去每位玩家输入的数得出差,并对差进行取绝对值操作得出最后差,差最小的玩家加一分,差最大的玩家减一分,...
  • 对所有玩家输入的数做如下处理:先求和再平均,将平均数乘以黄金分割数0.618得出黄金值,用黄金值分别减去每位玩家输入的数得出差,并对差进行取绝对值操作得出最后差,差最小的玩家加一分,差最大的玩家减一分,...
  • 对所有玩家输入的数做如下处理:先求和再平均,将平均数乘以黄金分割数0.618得出黄金值,用黄金值分别减去每位玩家输入的数得出差,并对差进行取绝对值操作得出最后差,差最小的玩家加一分,差最大的玩家减一分,...
  • 数据结构基本概念

    2020-08-09 10:00:35
    数据项:构成数据元素不可分割最小单位 数据>数据元素>数据项 数据对象:性质相同的数据元素的集合,是数据的子集 数据元素不是孤立的,它们之间存在某种关系,数据元素相互之间的关系称为结构 数据结构:...
  • 最小单元,不可再分割 1.2 一致性 相关的事务操作要么一致性成功,要么一致性失败; 1.3 隔离性 事务与事务之间具有不可见性; 1.4 持久性 一旦事务提交了,则永久性生效; 2. 事务的并发问题 2.1 脏读 事务A在读取...
  • 智能图像处理技术PDF

    热门讨论 2010-10-28 17:31:22
    9.2.6 用分数维描述纹理 9.2.7 Tamura纹理特征 9.3 形状特征分析 9.3.1 引言 9.3.2 基于轮廓的全局方法 9.3.3 基于轮廓的结构方法 9.3.4 基于区域的全局方法 9.3.5 基于区域的结构方法 本章参考文献 第10章...
  • 【电子书】智能图像处理技术

    热门讨论 2008-12-05 01:14:33
    9.2.6 用分数维描述纹理 9.2.7 Tamura纹理特征 9.3 形状特征分析 9.3.1 引言 9.3.2 基于轮廓的全局方法 9.3.3 基于轮廓的结构方法 9.3.4 基于区域的全局方法 9.3.5 基于区域的结构方法 本章参考文献 第10章...
  • 常用算法代码

    2017-09-11 11:26:53
    | 0-1 分数规划 22 | 最长有序子序列(递增/递减/非递增/非递减) 22 | 最长公共子序列 23 | 最少找硬币问题(贪心策略-深搜实现) 23 | 棋盘分割 23 | 汉诺塔 23 | STL 中的 PRIORITY_QUEUE 24 | 堆栈 24 |...

空空如也

空空如也

1 2 3
收藏数 57
精华内容 22
关键字:

最小分割分数