CodeForces1214A

系统管理员 2023-06-02 11:58 41阅读 0赞

[CodeForces1214A][]  
说起来你们可能不信,这题硬生生卡了我\\(1h\\),我想了背包,扩欧,二分....等等一坨办法.结果最后还是用了\\(bfs\\)过的.  
呃,代码一目了然,不用说吧...  
\\(Code:\\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define pb push_back using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; using std::queue ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } template < class T > inline void write(T x) { static T stk[100], top = 0; if (x == 0) { putchar('0'); return; } if (x < 0) { x = -x; putchar('-'); } while (x) { stk[++top] = x % 10; x /= 10; } while (top) { putchar(stk[top--] + '0'); } putchar ( 10 ) ; } const int N = 1e8 + 100 ; int dollar , euro , tot ; int d[] = { 1 , 2 , 5 , 10 , 20 , 50 , 100 } ; int e[] = { 5 , 10 , 20 , 50 , 100 , 200 } ; bool mk[N] ; queue < int > q ; inline void bfs (int x) { q.push ( x ) ; mk[x] = true ; while ( ! q.empty () ) { int j = q.front () ; q.pop () ; rep ( i , 0 , 6 ) { int tmp = j - d[i] ; if ( tmp >= 0 && ! mk[tmp] ) { mk[tmp] = true ; q.push ( tmp ) ; } } rep ( i , 0 , 5 ) { int tmp = j - e[i] ; if ( tmp >= 0 && ! mk[tmp] ) { mk[tmp] = true ; q.push ( tmp ) ; } } } return ; } signed main (int argc , char * argv[] ) { tot = rint () ; dollar = rint () ; euro = rint () ; MEM ( mk , 0 ) ; rep ( i , 0 , 6 ) d[i] *= dollar ; rep ( i , 0 , 5 ) e[i] *= euro ; bfs ( tot ) ; rep ( i , 0 , tot ) if ( mk[i] ) { write ( i ) ; break ; } return 0 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11469081.html

[CodeForces1214A]: http://codeforces.com/contest/1214/problem/A