A 国一共发行了几种不同面值的硬币,分别是面值 1 元,2 元,5 元,10 元,20 元,50 元, 100 元。假设每种面值的硬币数量是无限的,现在你想用这些硬币凑出总面值为 n 的硬币, 同时你想让选出的硬币中,不同的面值种类尽可能多;在面值种类尽可能多的情况下,你想 让选择的硬币总数目尽可能多,请问应该怎么选择硬币呢?
数据范围:
第一行包含一个数字𝑛,表示要凑出的面值。
输出两个整数,分别表示最多能有多少种类型的硬币以及在类型最多的情况下最多能用上多少枚硬币。
3
2 2
10
3 5
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @author wylu */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] coin = {0, 1, 2, 5, 10, 20, 50, 100}; int[] sum = new int[8]; for (int i = 1; i < coin.length; i++) { sum[i] += sum[i - 1] + coin[i]; } //策略为从小到大,每种面值的硬币用一个,剩下的全部用面值为1的硬币填充 for (int i = sum.length - 1; i > 0; i--) { if (n >= sum[i]) { System.out.println(i + " " + (n - sum[i] + i)); break; } } } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] coin = new int[]{1, 2, 5, 10, 20, 50, 100}; int n = Integer.parseInt(br.readLine().trim()); int type = 0, count = 0, sum = 0; for(int i = 0; i < coin.length; i++){ // 按面值升序遍历每种硬币,先保证硬币种类尽可能多 if(sum + coin[i] <= n){ sum += coin[i]; count ++; type ++; }else break; } if(sum < n) count += n - sum; // 不够的用1元硬币来凑,保证硬币数尽可能多 System.out.println(type + " " + count); } }
/* A 国一共发行了几种不同面值的硬币,分别是面值 1 元,2 元,5 元,10 元,20 元,50 元, 100 元。假设每种面值的硬币数量是无限的,现在你想用这些硬币凑出总面值为 n 的硬币, 同时你想让选出的硬币中,不同的面值种类尽可能多;在面值种类尽可能多的情况下,你想 让选择的硬币总数目尽可能多,请问应该怎么选择硬币呢? */import java.util.Scanner; public class Q3 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long value = sc.nextLong(); if(value>=188) { System.out.print(7+" "); System.out.println(value-181); } else if(value>=88) { System.out.print(6+" "); System.out.println(value-82); } else if(value>=38) { System.out.print(5+" "); System.out.println(value-33); } else if(value>=18) { System.out.print(4+" "); System.out.println(value-14); } else if(value>=8) { System.out.print(3+" "); System.out.println(value-5); } else if(value>=3) { System.out.print(2+" "); System.out.println(value-1); } else { System.out.print(1+" "); System.out.println(value); } } }
这题 case有问题
9999999999 7 1410065226
这个case是错误的,然后用如下代码能ac。
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long[] coins = new long[] {1, 2, 5, 10, 20, 50, 100}; long[] preSum = new long[9]; for (int i=1; i!=8; i++) { preSum[i] = coins[i-1] + preSum[i-1]; } preSum[8] = Long.MAX_VALUE; long lin = sc.nextLong(); int in = (int) lin; int i = 0; for (i=1; i!=8; i++) { if (preSum[i] > in) { break; } } System.out.printf("%d %d\n", i-1, in - preSum[i-1] + i-1); } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long[] coins = new long[] {1, 2, 5, 10, 20, 50, 100}; long[] preSum = new long[9]; for (int i=1; i!=8; i++) { preSum[i] = coins[i-1] + preSum[i-1]; } preSum[8] = Long.MAX_VALUE; long in = sc.nextLong(); int i = 0; for (i=1; i!=8; i++) { if (preSum[i] > in) { break; } } System.out.printf("%d %d\n", i-1, in - preSum[i-1] + i-1); } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[]{1, 2, 5, 10, 20, 50, 100}; int[] sum = new int[8]; for (int i = 1; i < 8; i++) { sum[i] = sum[i - 1] + arr[i - 1]; } for (int i = sum.length - 1; i > 0; i--) { if (n >= sum[i]) { System.out.println(i + " " + (n - sum[i] + i)); break; } } } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc =new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int[] res = getCoins(n); System.out.println(res[0] + " " + res[1]); } } // 贪心,从面值1 开始一个一个加面值种类,加到最后如果还有剩的,全部换成面值1的硬币 public static int[] getCoins(int n){ // res[0] : 种类数, res[1]:硬币数 int[] res = new int[2]; if (n - 1 >= 0){ n = n - 1; res[0]++; res[1]++; } if (n - 2 >= 0){ n = n - 2; res[0]++; res[1]++; } if (n - 5 >= 0){ n = n-5; res[0]++; res[1]++; } if (n - 10 >= 0){ n = n - 10; res[0]++; res[1]++; } if (n - 20 >= 0){ n = n - 20; res[0]++; res[1]++; } if (n - 50 >= 0){ n = n - 50; res[0]++; res[1]++; } if (n - 100 >= 0){ n = n - 100; res[0]++; res[1]++; } res[1] += n; return res; } }
#include<iostream> using namespace std; int main() { int N; cin>>N; if(N==1) cout<<1<<' '<<1; else if(N==2) cout<<1<<' '<<2; else if(N>=3&&N<8) cout<<2<<' '<<N-3+2; else if(N>=8&&N<18) cout<<3<<' '<<N-8+3; else if(N>=18&&N<38) cout<<4<<' '<<N-18+4; else if(N>=38&&N<88) cout<<5<<' '<<N-38+5; else if(N>=88&&N<188) cout<<6<<' '<<N-88+6; else cout<<7<<' '<<N-188+7<<endl; }
#include<iostream> #include<vector> using namespace std; int main(){ int money[7]={1,2,5,10,20,50,100}; int n; cin>>n; vector<int>sums(8); for(int i=0;i<7;i++){ sums[i+1]=sums[i]+money[i]; } int num; int res; if(sums[7]<n){ int sy = n-sums[7]; cout<<7<<" "<<7+sy<<endl; } else{ for(int i=1;i<8;i++){ if(sums[i]==n){ num=i; res = 0; break; } if(sums[i]>n){ num = i-1; res=n - sums[i-1]; break; } } cout<<num<<" "<<num+res<<endl; } return 0; }//题不难,贡献cpp