CF349B Color the Fence 题解 贪心

贪心

题意：
你一共有\(v\)元，给你数字\(1\)~\(9\)的价值，求出你能够买下的数字组成的最大数。

思路
首先，我们知道能够买下的数字个数越多，组成数字的位数就越多，结果自然就越大，那么，根据贪心策略，
我们可以先全买价格最便宜的数字(相同价格时，自然买更大的)。
参考代码：

  int v;
  cin>>v;
  vector<int> a(10);
  int minn=1e6;
  for(int i=1;i<=9;i++){
    cin>>a[i];
    minn=min(minn,a[i]);
  }
  if(v<minn) return cout<<-1,void();
  int val=1;
  for(int i=1;i<=9;i++) if(a[i]==minn) val=i;
  vector<int> ans;
  for(int i=0;i<v/a[val];i++) ans.eb(val);    
  for(auto x:ans) cout<<x;         

顺利写出代码，发现样例没问题，然后就会喜提Wrong answer on test 9，这是因为我们的钱可能并没有用完，还可以进行一些替换。
那么依旧根据贪心策略，我们可以从高位到低位枚举当前数字的每一位，从\(9\)~\(1\)查看是否可以进行替换即可。
参考代码：

  v%=a[val];//求出剩余的钱        
  for(int i=0;i<ans.size();i++){//从高位至地位进行枚举
     for(int j=9;j>val;j--){//小于val不用进行替换
        if(v+a[val]>=a[j]){//如果可以替换，一定是最优情况，那么直接break，看下一位即可。
            ans[i]=j;
            v+=a[val]-a[j];
            break;
        }
     }
  }   

完整代码