[洛谷题解] CF1214A Optimal Currency Exchange

发布于 2019-09-20  245 次阅读

题目链接：此处

题意翻译：

题目描述

Andrew参加了Olympiad of Metropolises，现准备回国，需要兑换货币。

现有如下面额的美元纸币：1 , 2 , 5 , 10 , 20 , 50 , 100，以及以下面额的欧元纸币：5 , 10 , 20 , 50 , 100 , 200（注意，不考虑500欧元纸币，因为在货币兑换窗口很难找到这种）。已知兑换1美元需要d卢布，1欧元需要e卢布，而Andrew有n卢布。

他可以兑换任意数量的美元和欧元（一种纸币可以兑换多次，可以美元和欧元混合），并且，他希望使兑换后手里剩余的卢布数尽可能少。请你写一个程序帮他解决问题（只需求出最小的剩余卢布数）。

输入格式

3行，3个正整数n,d,e。

输出格式

1行，1个非负整数表示最小剩余量。

数据范围

1 \leq n \leq 10^8

30 \leq d,e \leq 100

这题看似一个背包做的“最小剩余”问题，但是n太大，其实背包做不了。

我们注意到每种纸币可以兑换无限的数量。我们假设只兑换美元，那么美元数肯定是1的倍数；如果只兑换欧元，欧元数一定是5的倍数。

因此，我们暴力枚举，将x卢布用于兑换美元，那么这x卢布的剩余量是，x\ mod\ (d \times 1)。同理，n-x卢布会用于兑换欧元，剩余量是(n-x)\ mod\ (e \times 5)。

枚举的同时，我们维护ans=INF，并且枚举x是，更新ans为min(ans,x\ mod\ (d \times 1)+(n-x)\ mod\ (e \times 5))，最后输出ans，即可解决这个问题。容易发现，最多只要枚举10^8次，完全可以通过。

// status: [Accepted]
// oj:     [Codeforces]
#include<bits/stdc++.h>
using namespace std;
#ifndef DEBUG
    #define cerr if(0)cerr
#endif
// #ifndef OFFLINE_JUDGE
//     #define freopen if(0)freopen
// #endif
typedef long long ll;
typedef unsigned long long ull;
#define lll __int128_t
#define int ll
// #define int lll
#define For(i,ak,ioi) for(i=(ak);(((ak)<(ioi)) ? i<=(ioi) : i>=(ioi));i+=(((ak)<(ioi)) ? 1 : -1))
#define Rep(i,ak,ioi) for(int i=(ak);(((ak)<(ioi)) ? i<=(ioi) : i>=(ioi));i+=(((ak)<(ioi)) ? 1 : -1))
#define Range(i,ak,ioi,again) for(i=(ak);(((again)>0) ? i<=(ioi) : i>=(ioi));i+=(again))
#define Rap(i,ak,ioi,again) for(int i=(ak);(((again)>0) ? i<=(ioi) : i>=(ioi));i+=(again))
#define Memset(xt,ak) memset(xt,ak,sizeof(xt))
#define Reset(xt,ak,ioi,again) \
    for(int __reset_idx=ak;__reset_idx<=ioi;__reset_idx++) \
        xt[__reset_idx] = again
#define iter iterator
#define memgua memset
template<class _Tp>
inline _Tp readInteger() {
    _Tp ret=0,f=1;char c=getchar();
    while(c<'0' || c>'9') {if(c=='-') f*=-1; c=getchar();}
    while(c>='0' && c<='9') {ret=ret*10+f*(c-'0'); c=getchar();}
    return ret;
}
template<class _Tp>
void read(_Tp &x)  {x=readInteger<_Tp>();}
char readChar() { char c=getchar();while(isspace(c)) c=getchar();return c; }
void writeStr(char *s,int len,char _end='\0')
{for(int i=0;i<len;i++) putchar(s[i]);if(_end) putchar(_end);}
void writeStr(string s,char _end='\0') 
{for(unsigned i=0;i<s.length();i++) putchar(s[i]);if(_end) putchar(_end);}
template<class _Tp>
void writePositiveInteger(_Tp val)
{if(val==0)return;writePositiveInteger(val/10);putchar('0'+val%10);}
template<class _Tp>
void write(_Tp val,char _end='\0') {
    if(val==0) putchar('0');
    else if(val<0) {putchar('-');writePositiveInteger(-val);}
    else writePositiveInteger(val);
    if(_end) putchar(_end);
}

const int INF=7e14;
int v;
int c1;
int c2;
int arr[13] = {1,2,5,10,20,50,100,5,10,20,50,100,200};

signed main() {
    read(v);read(c1);read(c2);
    // for(int i=0;i<7;i++) arr[i]*=c1;
    // for(int i=7;i<13;i++) arr[i]*=c2;

    int ans=INF;
    for(int l=0;l<=v;l++) {
        int r=v-l;
        ans=min(ans,l%c1+r%(5*c2));
    }

    write(ans,'\n');
}
赏

undefined