2 条题解

  • 0
    @ 2025-10-8 16:55:17
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+10;
    int f[N];//f[i]记录第i个物品完成操作A完成时间
    struct node
    {
        int s, v;//s目前这台机器完成目前物品的结束的时间,v该机器速度
        bool operator<(node no)const{ return s>no.s; }//小根堆
    };
    priority_queue<node> q;//栈
    
    int main()
    {
        int n, m, a, b;scanf("%d", &n, &a, &b);
        for(int i=1, x; i<=a; i++)
        {
            scanf("%d", &x);
            q.push({x, x});//放入优先队列中
        }
        for(int i=1; i<=n; i++)
        {
            node no=q.top();//最小值
            q.pop();//把最小值弹出
            f[i]=no.s;//f[i]记录
            no.s+=no.v;//因为下一个物品也要用这台机器,结束时间要加no.v
            q.push(no);//再次压入栈
        }
        while(!q.empty()) q.pop();//记录完后,把q全部弹出去,priority_queue没有clear函数
        for(int i=1, x; i<=b; i++)
        {
            scanf("%d", &x);
            q.push({x, x});//记录
        }
        int ans=0;
        for(int i=n; i>=1; i--)
        {
            node no=q.top();//去除最小值
            q.pop();//把最小值弹出
            ans=max(ans, no.s + f[i]);//求最晚结束时间
            no.s+=no.v;//然后下一个物品要用这台机器 结束的时间就要+no.v
            //然而似乎开始用这台机器的操作该物品时候,可能上一个物品用这台
            //机器已经完成任务了,然而这并不影响
            q.push(no);
        }
        printf("%d %d\n", f[n], ans);//输出
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:55:02
      #include<bits/stdc++.h>
      using namespace std;
      const int N=1e6+10;
      int f[N];//f[i]记录第i个物品完成操作A完成时间
      struct node
      {
          int s,v;//s目前这台机器完成目前物品的结束的时间,v该机器速度
          bool operator<(node no)const{ return s>no.s; }//小根堆
      };
      priority_queue<node> q;//栈
      
      int main()
      {
          int n,m,a,b;scanf("%d%d%d",&n,&a,&b);
          for(int i=1,x; i<=a; i++)
          {
              scanf("%d",&x);
              q.push({x,x});//放入优先队列中
          }
          for(int i=1; i<=n; i++)
          {
              node no=q.top();//最小值
              q.pop();//把最小值弹出
              f[i]=no.s;//f[i]记录
              no.s+=no.v;//因为下一个物品也要用这台机器,结束时间要加no.v
              q.push(no);//再次压入栈
          }
          while(!q.empty()) q.pop();//记录完后,把q全部弹出去,priority_queue没有clear函数
          for(int i=1,x; i<=b; i++)
          {
              scanf("%d",&x);
              q.push({x,x});//记录
          }
          int ans=0;
          for(int i=n; i>=1; i--)
          {
              node no=q.top();//去除最小值
              q.pop();//把最小值弹出
              ans=max(ans,no.s+f[i]);//求最晚结束时间
              no.s+=no.v;//然后下一个物品要用这台机器 结束的时间就要+no.v
              //然而似乎开始用这台机器的操作该物品时候,可能上一个物品用这台
              //机器已经完成任务了,然而这并不影响
              q.push(no);
          }
          printf("%d %d\n",f[n],ans);//输出
          return 0;
      }
      • 1

      *【贪心】工序安排[USACO4.2]Job Processing

      信息

      ID
      1041
      时间
      500ms
      内存
      128MiB
      难度
      6
      标签
      递交数
      19
      已通过
      12
      上传者