「aoj2471～2480」の編集履歴（バックアップ）一覧に戻る

aoj2471～2480 - (2013/02/27 (水) 01:01:15) のソース

*aoj2476 Strange Currency System
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2476
与えられた通貨を組み合わせて色々な金額を作るとき、作れない最小金額を答えよ。

解法
２４００番台の問題とは思えないほど簡単な問題なのに正答者数が少ない問題です。
問題が英文であること２４００番台は難しいというイメージがあっておそらく多くの人がこの問題が簡単であると気付いてないのだと思います。
通貨を小さい順にソートして小さい方から足し合わせていって作れない数字が判明したらそれが答えです。


 #include<stdio.h>
 #include<vector>
 #include<algorithm>
 #include<iostream>
 int main(){
 	int n;
 	scanf("%d",&n);
 	std::vector<long long int> vec;
 	long long int a,sum=0;
 	for(int i=0;i<n;i++){
 		std::cin>>a;
 		vec.push_back(a);
 	}
 	std::sort(vec.begin(),vec.end());
 	for(int i=0;i<n;i++){
 		if(sum+1<vec[i]){
 			std::cout<<sum+1<<"\n";
 			return 0;
 		}
 		sum+=vec[i];
 	}
 	std::cout<<sum+1<<"\n";
 }