如果程式有顏色 那一定是...

The new "Avengers" movie has just been released! There are a lot of people at the cinema box office standing in a huge line. Each of them has a single 100, 50 or 25 dollars bill. A "Avengers" ticket costs 25 dollars.

Vasya is currently working as a clerk. He wants to sell a ticket to every single person in this line. 

Can Vasya sell a ticket to each person and give the change if he initially has no money and sells the tickets strictly in the order people follow in the line?

Return YES, if Vasya can sell a ticket to each person and give the change. Otherwise return NO.

Examples:

// === C Sharp ===

Line.Tickets(new int[] {25, 25, 50}) // => YES 
Line.Tickets(new int[] {25, 100})  
// => NO. Vasya will not have enough money to give change to 100 dollars

Solutions:

using System;
using System.Linq;
using System.Collections.Generic;
public class Line
    {
        public static string Tickets(int[] peopleInLine)
        { 
            const int TicketsPrice =25;
            Dictionary<int, int> VasyaWallet = new Dictionary<int, int>() { { 25, 0 }, { 50, 0 }, { 100, 0 } };
            foreach (int money in peopleInLine){
                int changeMoney = money - TicketsPrice;
                Dictionary<int, int> tempWallet = VasyaWallet;
                while (changeMoney > 0) {
                    var CurrentMoney = VasyaWallet.Where(em => em.Value > 0 && em.Key <=changeMoney).OrderByDescending(em => em.Key).FirstOrDefault();
                    if (CurrentMoney.Value > 0)
                    {
                        changeMoney -= CurrentMoney.Key;
                        tempWallet[CurrentMoney.Key]--;
                    }
                    else
                        return "NO";       
                }
                VasyaWallet = tempWallet;
                VasyaWallet[money]++;
            }
            return "YES";
        }
    }

當初完全不懂Linq 第一次接觸到linq就是在這網站看別人的solution才發現有這麼好用的工具   還去啃了某快快樂樂系列...  癢.. 好吃..

上方程式碼是我當初第二次想出來的解法  試圖用上linq來解決問題  

一開始我初始化我的錢包  定義25元硬幣 0個 50元硬幣0個 100元 0個

然後寫個for迴圈處理人群  然後判斷要不要找錢拉～  不用找就把錢直接收下  要找就要判斷我有沒有足夠的零錢去找

這段where就是找出我目前找能出的最大面值   然後找給人家   在進入迴圈看看還需不需要找   找到ChangeMoney歸0為止

using System;
using System.Linq;
using System.Collections.Generic;
public class Line
    {
        public static string Tickets(int[] peopleInLine)
        { 
            List<int> Vasya = new List<int>();
            foreach (int money in peopleInLine)
            {
                if (money == 25)
                    Vasya.Add(money);
                else if (money == 50)
                {
                    if (Vasya.Contains(25))
                    {
                       Vasya.Remove(25);
                       Vasya.Add(50);
                    }
                    else
                    {
                        return "NO";
                    }
                }
                else if (money == 100)
                {
                     if (Vasya.Contains(50) && Vasya.Where(x => x == 25).Count() >= 1)
                    {
                        Vasya.Remove(25);
                        Vasya.Remove(50);
                        Vasya.Add(100);
                    }
                    else if (Vasya.Where(x => x == 25).Count() >= 3)
                    {
                        Vasya.Remove(25);
                        Vasya.Remove(25);
                        Vasya.Remove(25);
                        Vasya.Add(100);
                    }
                    else
                        return "NO";
                }
            }
            return "YES";
        }
    }

上方程式碼是我當初第一次所寫出來的   這種做法我把每種可能性都列出來處理  如果面額一多可能寫到手斷掉

聽說這種作法似乎利用到貪婪演算法 不知道是不是類似的呢