cf536b——优先队列的运用

题目

题目大意：一个饭店有n种食物，每种食物有对应的价格和数量，然后有m个顾客，每个顾客需要$d_j$份第$t_j$种食物，如果该种食物数量不够，则选其它尽可能便宜的代替（出现同样价格的应选索引最小的）；如果所有的食物都不够该顾客，该顾客会吃完这些食物，并且不花钱。假设只有当前一个顾客服务完下一个才会来。

思路

模拟，根据题目所说的去做即可。唯一的困难是得到最便宜的食物，这需要对食物进行排序，由于同时还要记录原来的索引，所以用pair存储，放在优先队列中。

时间复杂度：$\mathcal{O}(m + n \log n)$

代码

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 using namespace std;

 typedef long long LL;

 typedef pair<int,int>  PII;        

 const int maxn =  + ;

 int n, m,r[maxn],c[maxn];

 priority_queue<PII, vector<PII>, greater<PII>>Q;   //优先第一维比较，第一维相同则根据第二维

 int main()

 {

     scanf("%d%d", &n, &m);

     for (int i = ; i <= n; i++)  scanf("%d", &r[i]);

     for (int i = ; i <= n; i++)

     {

         scanf("%d", &c[i]);

         Q.push(PII(c[i], i));

     }

     for (int i = ; i <= m; i++)

     {

         int t, d;

         scanf("%d%d", &t, &d);

         if (d <= r[t])

         {

             r[t] -= d;

             printf("%lld\n", 1LL * d * c[t]);

         }

         else

         {

             bool flag = false;

             LL ans = 1LL * r[t] * c[t];

             d -= r[t];

             r[t] = ;

             while (!Q.empty())

             {

                 while (!Q.empty() && r[Q.top().second] == )  Q.pop();

                 if (Q.empty())  break;

                 PII now = Q.top();

                 if (d <= r[now.second])

                 {

                     r[now.second] -= d;

                     ans += 1LL * d * now.first;

                     flag = true;

                     printf("%lld\n", ans);

                     break;

                 }

                 else

                 {

                     ans += 1LL * r[now.second] * now.first;

                     d -= r[now.second];

                     r[now.second] = ;

                     Q.pop();

                 }

             }

             if (!flag)  printf("0\n");

         }

     }

     return ;

 }

参考链接：https://codeforces.com/blog/entry/64928

巴特西

cf536b——优先队列的运用

题目

思路

代码

最新文章

热门文章