UVA 11264: Coin Collector

http://uva.onlinejudge.org/external/112/11264.html

原问题是这样:

小明去国外玩,想兑换些货币。他希望每种面值的货币都兑换点。但是兑换处的人可不理会他这个需求,兑换处的原则是,尽量挑选面值最大的给他。比如货币的面值是100、50、20、10、5、2、1,你要76块钱,那我先给你50,还差你26。于是再给你20,还差6块。那我再给5块,再给1块。嗯……一般人都是这样给钱的吧?

但是小明就是喜欢收集钱币啊。假如货币的面值种类已知,问用这种方法最多能换到多少种?假设小明很富有,钱无限多。

例如:

1 2 4 8 16 32 6种

1 3 6 8 15 20 4种

1 3 6 8 11 3种

答:

假设输入的数组为A[1...n] ,它代表了N中不同面值。假设我们已经按照从小到大排序,其中A[1]最小,A[n]最大。

如果小明拿m元换得了k种货币,那么m最小是多少? 答:把这几种货币的面值加起来。

另外,A[n](即面值最大的)一定会被选中,反证:如果花了m元却没有选中它,可知m<A[n],于是用m+A[n]元去兑换可以得到一个更优解。

假设S(i)是A[1]...A[i] 中那些被选中的货币的面值的和。那么一定有 S(i) < A[i+1]。

假如我们已经知道最优解是k种货币,那么它对应的具体哪k种呢?这个答案是否唯一? 不。 拿1 3 4来说, 1 4 和 3 4 都是最优解。

所以我们想办法构造一个这样的序列出来。按照规则:如果有S(i-1) + A[i] < A[i+1],那么A[i] 被选中。

首先,这个序列很显然是一个合法的序列,所以它是解。其次,要证明它是最优的,即,不存在比它更长的合法序列。

long resolve(std::vector<long>& nums){
  if(nums.size()<=2) return nums.size();
  std::sort(nums.begin(),nums.end());
  nums.push_back(LONG_MAX);
  //now,nums.size()>=3
  long ret(2);
  long sum(nums[0]+nums[1]);
  for(size_t i=2;i!=nums.size()-1;++i){
    if(sum+nums[i]<nums[i+1]){
      sum+=nums[i];
      ret++;
    }
  }
  return ret;
}

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥