发工资

//编程马拉松
//https://www.nowcoder.com/practice/395e41c81109483a9ee24d387d939b44?tpId=3&&tqId=10910&rp=3&ru=/activity/oj&qru=/ta/hackathon/question-ranking

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
    int money[7] = {100, 50, 20, 10, 5, 2, 1};
    int n, x; //n为人数，x为准备的人民币张数
    int salary;
    while (cin >> n && n > 0)
    {
        x = 0;
        for (int i = 0; i < n; ++i)
        {
            cin >> salary;
            for (int j = 0; j < 7; ++j)
            {
                if (salary / money[j] > 0)
                {
                    x += (salary / money[j]);
                    salary %= money[j];
                }
                if (salary == 0)
                    break;
            }
        }
        cout << x << endl;
    }
}

贪心算法
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<functional>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <exception>
#include <iomanip>
#include <memory>
#include <sstream>

using namespace std;

int main(int argc, char** argv)
{
	//freopen("in.txt", "r", stdin);
	int n;
	int money[]{100, 50, 20, 10, 5, 2, 1};
	while (cin >> n && n >= 0)
	{
		int count = 0;
		int salary;
		for (int i = 0; i < n; ++i)
		{
			cin >> salary;
			for (int i = 0; i < 7; ++i)
			{
				count += salary / money[i];
				salary %= money[i];
			}
		}
		cout << count << endl;
	}

	return 0;
}

/*
 * 本题有两种解法：
 * 1、贪心：
 *  其实这道题乍眼一看就是用贪心做的，但是贪心有一个缺陷，就是有时候不能取到最优，但是在本题，用贪心就可以，思路很简单，把给的钱从大到小排序，每次都尽量取最大的即可。代码如下：
*/
public class Main {
	public static void main(String[] args) {
	    Scanner sc=new Scanner(System.in);
	    int[] mon={100,50,20,10,5,2,1};
	    while (sc.hasNext()) {
	        int n=sc.nextInt();
	        int[] input=new int[n];
	        int sum=0;
	        for(int i=0;i<n;i++){
	            input[i]=sc.nextInt();
	            int temp=input[i];
	            for(int j=0;j<mon.length;j++){
	            	sum+=(temp/mon[j]);
	            	temp=temp%mon[j];
	            	if(temp==0){
	            		break;
	            	}
	            }
	        }
	        System.out.println(sum);
	    }
	     
	}
}
/ * 
  * 2、动态规划：
   其实动态规划是我们经常用的一个思想，也是能保证取到最优解的，如果这道题稍有变动的话，贪心就做不了，只能用动态规划，但是动态规划有一个缺点，用空间换时间，动态打表会浪费很多内存，就本题来说，我最开始用动态规划做，自己再本机运行正确，但是提交上去就提示运行错误（一般是数组越界），为什么会出现这样的问题呢，因为测试用例有边界值，举个例子来说：如果给这样的一个测试用例:
3
1 2 2147483647
就会出现java.lang.NegativeArraySizeException这个异常，因为我们要开辟2147483647+1个数组，这样导致了开辟数组的长度（当然也超出了int的范围），超出了JVM的设置，就会报错，当然也可以修改JVM的参数，但是我们只能修改自己本机上的，改不了这个测试程序后台的参数，所以，如果自己运行正确，提交运行错误，应该是这个原因，所以，动态规划虽然是个好办法，但是如果测试数据过大，就会很费内存，有时候会报错，所以我们针对不同的题需要有合适的解法，这个题用贪心的话，就不会存在这个数组越界的问题。
下面贴上我自己动态规划的代码，虽然下面代码没有通过测试用例，但是这个想法比较好，可以用的其他题，如果有什么问题，希望大家指出问题。
 */
public class Main {
	 public static void main(String[] args) {
			Scanner sc=new Scanner(System.in);
			int[] mon={1,2,5,10,20,50,100};
			System.out.println(Integer.MAX_VALUE);
			while (sc.hasNext()) {
				int n=sc.nextInt();
				int[] input=new int[n];
				int max=0;
				int sum=0;
				for(int i=0;i<n;i++){
					input[i]=sc.nextInt();
					if(input[i]>max)
						max=input[i];
				}
				int [] dp=new int[max+1];
				dp[0]=0;
		        for(int i=0;i<mon.length;i++){
		        	for(int j=mon[i];j<=max;j++){
		        		dp[j]=dp[j-mon[i]]+1;
		        	}
		        }
		        for(int i=0;i<n;i++){
		        	sum+=dp[input[i]];
		        }
		        System.out.println(sum);
			}
			
		}
}

package main
 
import (
    "fmt"
    "io"
)
 
func main() {
    n:=0
    num:=[]int{}
    count:=0
    for {
        _, err := fmt.Scan(&n)
        if err == io.EOF {
            break
        }
        
        for i:=0;i<n;i++{
            x:=0
            fmt.Scan(&x)
            num=append(num, x)
            m_100:=x/100
            m_50:=x%100/50
            m_20:=x%100%50/20
            m_10:=x%100%50%20/10
            m_5:=x%100%50%20%10/5
            m_2:=x%100%50%20%10%5/2
            m_1:=x%100%50%20%10%5%2/1
            
            count=count+m_100+m_50+m_20+m_10+m_5+m_2+m_1
        }
        fmt.Println(count)
        count=0
    }
}

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		// 要用贪心做,动态规划会越界
		Scanner sc = new Scanner(System.in);
		int money[] = {100, 50, 20, 10, 5, 2, 1};
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int sum = 0;
			for (int i = 0; i < n; i ++ ) {
				int m = sc.nextInt();
				for (int j = 0; j < money.length; j ++ ) {
					sum += m / money[j];
					m = m % money[j];
					if(m == 0) break;
				}
			}
			System.out.println(sum);
		}
	}
}

// write your code here cpp
//vs通过用例，为什么这就不通过了？？？？？？？？？？？？？？？？？
/*#include<iostream>

using namespace std;
int main(){
    int a[7]={100,50,20,10,5,2,1};
    int n,m;
    int count=0,k=0;
    cin>>n;
    while(n--){
        cin>>m;
        for(int i=0;i<7;i++){
            if(a[i]>m)continue;
            k=m/a[i];
            m=m-k*a[i];
            count=k+count;
        }
    }
    cout<<count<<endl;
    return 0;
}*/
// write your code here cpp
// write your code here cpp
//搞定
#include<iostream>

using namespace std;
int main(){
	int a[7] = { 100, 50, 20, 10, 5, 2, 1 };
	int n, m;
	int count = 0, k = 0;
    //cin >> n;
   while(cin>>n){
       count=0;
	while (n--){
		cin >> m;
		for (int i = 0; i<7; i++){
			if (a[i]>m)continue;
			k = m / a[i];
			m = m - k*a[i];
			count = k + count;
		}
        //n--;
	}
	cout << count<<endl;
   }
	return 0;
}

#include<stdio.h>
int main()
{
	int n,cnt,exp;
	while(scanf("%d",&n) != EOF)
	{
		cnt = 0;
		while(n--)
		{
			scanf("%d",&exp);
			cnt += exp/100;
			exp = exp%100;
			cnt += exp/50;
			exp = exp%50;
			cnt += exp/20;
			exp = exp%20;
			cnt += exp/10;
			exp = exp%10;
			cnt += exp/5;
			exp = exp%5;
			cnt += exp/2;
			exp = exp%2;
			cnt += exp/1;
		}
		printf("%d\n",cnt);
	}
    return 0;
}

//我想说题设好牵强。。。现在发工资还用现金的哇。。。
#include "iostream" 
using namespace std;
//功能：找到工资x是在什么范围，并
//扣掉该币值的若干倍（有的直接减去该币值）
 //返回该币值张数，间接返回余额*p 
int findpos(int x,int *p){
*p = x; 
if(x >= 100) {*p = x%100; return (x/100);}
else if(x >= 50 && x < 100) {*p = x-50; return 1;}
else if(x >= 20 && x <50) {*p = x%20; return (x/20);}
else if(x >= 10 && x < 20) {*p = x-10; return 1;}
else if(x >= 5 && x < 10) {*p = x-5; return 1;}
else if(x >= 2 && x < 5) {*p = x%2; return (x/2);}
else {*p = 0; return 1;}
}
//功能：计算单笔工资 各种币值组合的总张数z
int count(int x){ 
   int z = 0;
   int *p;
   p = new int(x); //或p = &x;
   while(*p>0){
  z += findpos(*p,p);//累加每一种币值的张数 

}                  //每一次余额*p都减少，用余额继续找
  return z;
}

int main(void){ 
	int n,s,i;
	while(cin>>n){  //输入个数n
	   int a[n];//开辟n个元素的数组空间存工资 
	    for(i = 0;i<n;i++){cin>>a[i];}//输入工资
	    s = 0;
		for(i = 0;i<n;i++){
		s += count(a[i]); //累加各笔工资的钱币张数
	    }
	    cout<<s<<endl; 
	}
return 0;
}