https://codeforces.com/contest/1106/problem/B

C++版本一

題解：

貪心

按價格排序，作為不足時的取菜順序，設一個指針記錄，如果指針到n+1，說明沒有菜可以取了

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; ll t,n,m,k,q,d; ll ans,cnt,flag,temp; ll a[N]; ll c[N]; char str; struct node{ll id,c;bool operator <(const node &S)const{return c<S.c;} }e[N]; int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%I64d%I64d",&n,&m);for(int i=1;i<=n;i++){scanf("%I64d",&a[i]);}for(int i=1;i<=n;i++){scanf("%I64d",&e[i].c);e[i].id=i;c[i]=e[i].c;}sort(e+1,e+n+1);int pos=1;while(m--){scanf("%I64d%I64d",&t,&d);ans=0;if(a[t]>0){if(a[t]>=d){ans+=c[t]*d;a[t]-=d;d=0;}else{ans+=c[t]*a[t];d-=a[t];a[t]=0;}}while(d>0&&pos<=n){ //cout<<e[pos].id<<" "<<a[e[pos].id]<<d<<" "<<ans<<endl;if(a[e[pos].id]>0){if(a[e[pos].id]>=d){ans+=c[e[pos].id]*d;a[e[pos].id]-=d;d=0;}else{ans+=c[e[pos].id]*a[e[pos].id];d-=a[e[pos].id];a[e[pos].id]=0;pos++;}}else{pos++;}}if(d>0){ans=0;}cout<<ans<<endl;}//cout << "Hello world!" << endl;return 0; }

C++版本二

#include<stdio.h> #include<stdlib.h> #include<ctype.h> #include<math.h> #include<string.h> #include<queue> #include<algorithm> #include<vector> #define ll long long #define pb push_back #define INF 0x3f3f3f3f; #define test printf("here!!!") using namespace std; const int mx=1e5+10; const int mod=998244353; struct Node {int v;int id; }hgf,dzb; bool operator <(const Node &a,const Node &b) {if (a.v!=b.v) return a.v>b.v;else return a.id>b.id; } priority_queue<Node>q; int a[mx]; int c[mx]; int vis[mx]; int main() {int n,m,t,d;scanf("%d%d",&n,&m);for (int i=1;i<=n;++i) scanf("%d",&a[i]);for (int i=1;i<=n;++i){scanf("%d",&c[i]);hgf.v=c[i];hgf.id=i;q.push(hgf);}while (m--){ll cost=0;scanf("%d%d",&t,&d);if (a[t]>=d){a[t]-=d;cost=1ll*d*c[t];if (a[t]==0) vis[t]=1;d=0;}else{cost=1ll*a[t]*c[t];d-=a[t];a[t]=0;vis[t]=1;while (d&&!q.empty()){dzb=q.top();q.pop();if (a[dzb.id]>=d&&!vis[dzb.id]){a[dzb.id]-=d;cost+=1ll*d*dzb.v;d=0;if (a[dzb.id]==0) vis[dzb.id]=1;else{q.push(dzb);}}else if (a[dzb.id]<d&&!vis[dzb.id]){cost+=1ll*a[dzb.id]*dzb.v;d-=a[dzb.id];a[dzb.id]=0;vis[dzb.id]=1;}}}if (d) printf("0\n");else printf("%I64d\n",cost);} }

?

總結

以上是生活随笔為你收集整理的Lunar New Year and Food Ordering的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。