本文共 2125 字，大约阅读时间需要 7 分钟。
#include #include #include #include #include #include #include #include #include #include #include #include #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 #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