2 条题解

  • 0
    @ 2025-10-8 17:01:39
    #include <bits/stdc++.h>
    using namespace std;
    priority_queue<int> Q;
    struct node{int x, u;}a[11000];
    bool cmp(node n1, node n2){ return n1.x < n2.x;}
    
    int n, L, P;
    
    bool pd()
    {
        int np = P;
        for(int i = 2; i <= n; i++)
        {
            np -= (a[i].x - a[i-1].x);
            if(np < 0) return 0;
            np += a[i].u;
        }
        return 1;
    }
    int main()
    {
        scanf("%lld", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d%d", &a[i].x, &a[i].u);
    
        scanf("%d%d", &L, &P);
        for(int i = 1; i <= n; i++)
            a[i].x = L - a[i].x;
        a[n+1].x = 0, a[n+1].u = 0;
        a[n+2].x = L, a[n+2].u = 0;
        n += 2;
        sort(a + 1, a + n + 1, cmp);
        
        if(pd() == 0){ printf("-1"); return 0; }
        
        int ans = 0, np = P;
        for(int i = 2; i <= n; i++)
        {
            np -= (a[i].x - a[i-1].x);
            while(np < 0)
            {
                np += Q.top();
                Q.pop();
                ans++;
            }
            Q.push(a[i].u);
        }
        printf("%d\n", ans);
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:01:30
      #include<bits/stdc++.h>
      using namespace std;
      priority_queue<int>Q;
      struct node{int x,u;}a[11000];
      bool cmp(node n1,node n2){ return n1.x<n2.x;}
      
      int n,L,P;
      
      bool pd()
      {
          int np=P;
          for(int i=2;i<=n;i++)
          {
              np-=(a[i].x-a[i-1].x);if(np<0) return 0;
              np+=a[i].u;
          }
          return 1;
      }
      int main()
      {
          scanf("%lld",&n);
          for(int i=1;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].u);
      
          scanf("%d%d",&L,&P);
          for(int i=1;i<=n;i++)a[i].x=L-a[i].x;
          a[n+1].x=0,a[n+1].u=0;
          a[n+2].x=L,a[n+2].u=0;
          n+=2;
          sort(a+1,a+n+1,cmp);
          
          if(pd()==0){ printf("-1"); return 0; }
          
          int ans=0,np=P;
          for(int i=2;i<=n;i++)
          {
              np-=(a[i].x-a[i-1].x);while(np<0){np+=Q.top();Q.pop();ans++;}
              Q.push(a[i].u);
          }
          printf("%d\n",ans);
          return 0;
      }
      • 1

      *【贪心】奶牛探险 [USACO05OPEN] Expedition G

      信息

      ID
      2607
      时间
      1000ms
      内存
      128MiB
      难度
      3
      标签
      递交数
      36
      已通过
      21
      上传者