本文共 4628 字，大约阅读时间需要 15 分钟。

Student Arseny likes to plan his life for n days ahead. He visits a canteen every day and he has already decided what he will order in each of the following n days. Prices in the canteen do not change and that means Arseny will spend ci rubles during the i-th day.

There are 1-ruble coins and 100-ruble notes in circulation. At this moment, Arseny has m coins and a sufficiently large amount of notes (you can assume that he has an infinite amount of them). Arseny loves modern technologies, so he uses his credit card everywhere except the canteen, but he has to pay in cash in the canteen because it does not accept cards.

Cashier always asks the student to pay change-free. However, it's not always possible, but Arseny tries to minimize the dissatisfaction of the cashier. Cashier's dissatisfaction for each of the days is determined by the total amount of notes and coins in the change. To be precise, if the cashier gives Arseny x notes and coins on the i-th day, his dissatisfaction for this day equals x·wi. Cashier always gives change using as little coins and notes as possible, he always has enough of them to be able to do this.

"Caution! Angry cashier"

Arseny wants to pay in such a way that the total dissatisfaction of the cashier for n days would be as small as possible. Help him to find out how he needs to pay in each of the n days!

Note that Arseny always has enough money to pay, because he has an infinite amount of notes. Arseny can use notes and coins he received in change during any of the following days.

5 42117 71 150 243 2001 1 1 1 1

791 171 02 02 432 0

3 0100 50 501 3 2

1501 01 00 50

5 42117 71 150 243 2005 4 3 2 1

2301 171 01 503 02 0

题意：

给出n，m表示你初始有m个硬币。有无限多100元的钞票

接下来一行n个数，表示你每天的花费。

然后一行n个数，表示收银员不高兴系数wi

每天你如果刚好给收银员那么多钱而不用找零，那么这一天的不高兴值为0，若要找零x元，那么这天的不高兴值为wi*x。

前面找零得到的硬币可以在后面几天使用。

问，怎样能够使得收银员n天总的不高兴值最小。输出总的不高兴值

并输出n行，每行两个数a，b 表示用a张100元钞票，b个硬币。

题解：

其实这题和前面那个括号匹配的题一样的做法，

对于任意一天，设x为模100后的部分。如果全交硬币，那么硬币数-x，如果多交1张纸币，硬币数-x+100,总值加上 w[i]*(100-x)。于是先每一天都按交硬币减去需要硬币数，不够的情况就是减完为负。由于是按时间顺序一天天来的，那么就说明在这一天即其之前的天里，必须有一天是破百元的钱的。选择方法是找其中对总值加的最少的。用set写就是.begin（），也可以用优先队列重载运算符做就是top的元素。并且又得到100枚硬币后一定可以够交钱，采用这样的贪心策略进行即可。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define rep(i,a,n) for (int i=a;i
          
           =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
           
             VI;typedef long long ll;typedef pair
            
              PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=1e5+100;struct Ans{ int a,b; int w,id; Ans(int x=0,int y=0,int z=0,int u=0):a(x),b(y),w(z),id(u) {} bool operator < (const Ans &t)const{ return (100-b)*w>(100-t.b)*t.w; }}ans[maxn];int c[maxn],w[maxn];priority_queue
             
               q;int main(){ int n; ll m; scanf("%d%lld",&n,&m); rep(i,1,n+1) scanf("%d",&c[i]); rep(i,1,n+1) scanf("%d",&w[i]); ll res=0; rep(i,1,n+1) { if(c[i]%100) { int p=c[i]%100; if(m>=p) { q.push(Ans(c[i]/100,c[i]%100,w[i],i)); ans[i]=Ans(c[i]/100,c[i]%100); m-=p; } else { if(!q.empty()) { q.push(Ans(c[i]/100,c[i]%100,w[i],i)); m-=c[i]%100; ans[i]=Ans(c[i]/100,c[i]%100); while(m<0&&!q.empty()) { Ans t=q.top(); q.pop(); res+=(100-t.b)*t.w; m+=100; ans[t.id].a++,ans[t.id].b=0; } } else { ans[i]=Ans(c[i]/100+1,0); m+=100-c[i]%100; res+=w[i]*(100-c[i]%100); } } } else ans[i]=Ans(c[i]/100,0); } printf("%lld\n",res); rep(i,1,n+1) printf("%d %d\n",ans[i].a,ans[i].b); return 0;}
             
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/fouzhe/article/details/56499000 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！