C++ / Python 折價問題
問題 : 連續集數 & 單集多本的優惠活動
書店在賣書一本書定價100元
買第一集 + 買第二集 95折
買第一集 + 買第二集 + 買第三集 9折
買第一集 + 買第二集 + 買第三集 + 買第四集 8折
買第一集 + 買第二集 + 買第三集 + 買第四集 + 買第五集 75折
每集最多買5本~
EX:
使用者買第一集*2 + 第二集*1 = 290
(100+100) * 0.95 + 100 = 290
使用者買第一集*1+ 第二集*1+ 第三集*1 = 270
(100+100+100) * 0.9 = 290
輸入:
[2,1,0,0,0]
[1,1,1,0,0]
輸出:
290
270
很像購物車的問題
題目要求有連續的集數才有優惠，例如 : 買1、2、3 或 4、5
另外的優惠是同一集買多本，例如第1集買2本也打9折~~
那可以發現集數共有5集，那這題的邏輯是要先處裡有連續集數的優惠，把連續處理完後再把單集多本的優惠解決，注意在處裡單集多本之前要記得把優惠過的本子的數量扣掉，剩下的才會是單集多本的數量。
流程大概長這樣，假如買 : 2 2 1 2 2-> 1 1 0 1 1 -> 0 0 0 1 1 -> 0 0 0 0 0，所以是一步一步確認總體的連續集數，過程中會記錄某一集最少的本子，目的是為了之後算錢能一次算完，算完扣掉之後才會出現0，之後從頭找，扣掉.... 直到從頭找的地方等於0，在往下一個繼續找，最後答案就出來了。
Python:
def Input(_list):
arr=[]
for i in _list:
if i != ' ':
arr.append(int(i))
return arr
def method(_list,buylength):
OFF = [100,100,95,90,80,75]
price = 0
index1 = 0
while(index1<buylength):
if(_list[index1] == 0):
index1+=1
continue #回13行
index2 = index1+1 #index1負責停一個點，index2負責去掃描
mimSizeOfBook = _list[index1] #左到右第一個非0的點
while(index2<buylength and _list[index2]>0): #(做到大於長度 且 掃到的值都大於0)
mimSizeOfBook=min(mimSizeOfBook,_list[index2]) #找最小，目的在一次把優惠算完
index2+=1
saleLo = index2 - index1 #連續集數的長度
price += OFF[saleLo] * mimSizeOfBook * saleLo #連續集數的錢
while(index2>index1): #扣掉已經算好的書
index2-=1
_list[index2]-=mimSizeOfBook
print(_list)
return price
while(1):
ibuy = Input(input())
BOOK_int = len(ibuy)
ans = method(ibuy,BOOK_int)
print(ans)
C++:
#include <iostream>
#include <vadefs.h>
using namespace std;
const int BOOK_LEN = 5;
const int OFF[] = { 100, 100, 95, 90, 80, 75 };
void Input(int* books, const int bookLen)
{
for (int index = 0; index < bookLen; index++)
cin >> books[index];
}
int Process(int* books, const int bookLen)
{
int price = 0;
int index1 = 0;
while (index1 < bookLen)
{
if (books[index1] == 0)
{
index1++;
continue;
}
int index2 = index1 + 1;
int minSize = books[index1];
while (index2 < bookLen && books[index2] > 0)
{
minSize = min(minSize, books[index2]);
index2++;
}
int episode = (index2 - index1);
price += (minSize * OFF[episode]) * episode;
while (index2 > index1)
{
index2--;
books[index2] -= minSize;
}
}
return price;
}
int main()
{
int* books = new int[BOOK_LEN];
Input(books, BOOK_LEN);
int price = Process(books, BOOK_LEN);
delete[] books;
cout << price << endl;
system("pause");
return 0;
}
這題是我面試的白板題，供大家參考，假如你可以在半小時內做完，那其他題就別怕了~~
留言列表
