This is my participation 11 The fourth of the yuegengwen challenge 2 God , Check out the activity details ：2021 One last more challenge

Thank you very much for reading this article ~ welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~ It's not hard to give up , But persistence must be cool ~ I hope all of us can make a little progress every day ~ This paper is written by The white hat of the second leader https://juejin.cn/user/2771185768884824/posts Original blog ~

---

LCP 06. Take the coin ：

It's on the table n Money is deducted from the pile , The number of each heap is stored in the array coins in . We can choose any pile at a time , Take one or two of them , Ask for the minimum number of times to deduct money from all efforts .

Examples 1

 Input ：
	[4,2,1]
	
 Output ：
	4

 explain ：
	 The first pile of force deduction coins needs to take at least  2  Time , The second pile needs at least  1  Time , The third pile needs at least  1  Time , in total  4  You can get it all at once .
 Copy code 

Examples 2

 Input ：
	[2,3,10]

 Output ：
	8
 Copy code 

Tips

• 1 <= n <= 4
• 1 <= coins[i] <= 10

---

analysis

• This algorithm problem two is in charge. I believe everyone can do it , But it has been carefully optimized ？
• Pick one at a time , Obviously, each pile does not affect each other , So it is the desired result to accumulate and calculate the sum of at least several times for each pile .
• You can take one or two at a time , Children also know how to take more , It must be the fastest to take two at a time , But if a pile of coins is odd , Then you can only take one at the last time .
• Direct division 2 Words , Odd numbers will be counted less once , So we need to judge odd or even , If it's an odd number, count it again .
• Can we handle odd and even numbers in a unified way ？ You can directly add and divide again and again to two (coins[i] + 1) / 2. If it was even , Then it does not affect the division by 2 Result , If it is an odd number, it will divide the whole by 2 Add one... To the result .
• Bit operations are faster than arithmetic operations , So we can optimize it to (coins[i] + 1) >> 1.

---

Answer key

java

class Solution {
    public int minCount(int[] coins) {
        int ans = 0;
        for (int c : coins) {
            ans += (c + 1) >> 1;
        }
        return ans;
    }
}
 Copy code 

---

c

int minCount(int* coins, int coinsSize){
    int ans = 0;
    for (int i = 0; i < coinsSize; ++i) {
        ans += (coins[i] + 1) >> 1;
    }
    return ans;
}
 Copy code 

---

c++

class Solution {
public:
    int minCount(vector<int>& coins) {
        int ans = 0;
        for (int& c : coins) {
            ans += (c + 1) >> 1;
        }
        return ans;
    }
};
 Copy code 

---

python

class Solution:
    def minCount(self, coins: List[int]) -> int:
        return sum([(c + 1) >> 1 for c in coins])
 Copy code 

---

go

func minCount(coins []int) int {
    ans := 0
	for _, c := range coins {
		ans += (c + 1) >> 1
	}
	return ans
}
 Copy code 

---

rust

impl Solution {
    pub fn min_count(coins: Vec<i32>) -> i32 {
        coins.iter().map(|c|{
            (c + 1) >> 1
        }).sum()
    }
}
 Copy code 

---

---

Original title transmission gate ：https://leetcode-cn.com/problems/na-ying-bi/

---