acsdw12 2020-06-14 08:57 采纳率: 100%
浏览 231
已采纳

巧克力加工c++问题请速解

题目描述

儿童节到了,幼儿园老师要给小朋友做一些手工创意巧克力,做法就是买了了一些普通条状巧克力进行加工。现有n块巧克力,知道它们的长度和重量。老师们需要用机器一根一根地加工这些巧克力。该机器在加工过程中需要一定的准备时间,是用于清洗机器,调整工具和模板的。需要的准备时间如下:
(1)第一根巧克力1min的准备时间;
(2)在加工了一根长为x,重为w的巧克力之后,接着加工一根长为xx(x<=xx),重为ww(w<=ww)的巧克力是不需要任何准备时间的。否则需要一分钟的准备时间。
老师们n条巧克力,你要找到最少的准备时间。例如现在有长和重分别为(4,9),(5,2),(2,1),(3,5)和(1,4)的五根巧克力,那么所需准备时间最少为2min,顺序为(1,4),(3,5),(4,9),(2,1),(5,2)。

输入
第一行是一个整数n(1<=n<=5000),表示有多少条巧克力;
第二行包括n*2个整数,表示了x1,w1,x2,w2......xn,wn,这些数均不大于10000,其中xi和wi表示第i巧克力的长度和重量。
输出
输出以分钟为单位的最少准备时间。
样例输入 Copy
5
4 9 5 2 2 1 3 5 1 4
样例输出 Copy
2
\

  • 写回答

1条回答 默认 最新

  • threenewbee 2020-06-14 10:07
    关注
    #include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    
    #define N 5000+10
    struct node{
        int l;
        int w;
    };
    struct node num[N];
    int cmp(struct node a,struct node b)
    {
        if(a.l == b.l )
            return a.w < b.w ;
        return a.l < b.l ;
    }
    int main()
    {
        int t,book[N];
        int n,i,j,sumtime,sum,x;
        scanf("%d",&t);
        while( t --)
        {
            scanf("%d",&n);
            for(i = 1; i <= n; i ++)
                scanf("%d%d",&num[i].l ,&num[i].w );
            sort(num+1,num+n+1,cmp);
            memset(book,0,sizeof(book));
            sumtime = 0;
            sum = n;
            for(i = 1; i <= n; i ++)
            {
    
                if(!book[i])
                {
                    x = i;
                    book[i] = 1;
                    sum --;
                    for(j = i+1; j <= n; j ++)
                    {
                        if(num[x].l <= num[j].l &&num[x].w <= num[j].w&&!book[j])
                        {
                            book[j] = 1;
                            x = j;
                            sum --;
                        }
                    }
                    sumtime++;
                }
                if(sum <= 0)
                    break;
            }
            printf("%d\n",sumtime);
    
        }
        return 0;
     } 
    
    

    https://blog.csdn.net/hello_sheep/article/details/75915986

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?
  • ¥15 ubuntu系统下挂载磁盘上执行./提示权限不够
  • ¥15 Arcgis相交分析无法绘制一个或多个图形
  • ¥15 关于#r语言#的问题:差异分析前数据准备,报错Error in data[, sampleName1] : subscript out of bounds请问怎么解决呀以下是全部代码:
  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型