免费午餐题解

题目描述

为了增加顾客,Sally的店铺决定提供免费午餐,顿时门庭若市,但是不久Sally的原材料不足了….因此Sally决定公布一项决定:凡是来本店吃免费午餐的,一天吃能吃一次,吃的数量必须比上一次吃的少, 点的必须在上一次后面，且免费午餐将只有N个种类任君选择,为了能吃到最多的免费午餐,你将如何安排每日吃的数量呢?

输入格式

第一行一个数N，表示免费午餐的种类（0<=N<=100000)
第二行N个数，表示每个免费午餐的数量（0<=数量<=100000）

输出格式

一个数,表示最多能吃多少天

分析：其实是求最长单调递减子序列。使用二分法依次求解：

#include <iostream>#include <vector>using namespace std;int total = 0;vector<int> v1;vector<int> v2;//求递减数列的上界位置int binarySearch(int key,int lowIndex,int highIndex){ if(lowIndex==highIndex) { if(key<v2[lowIndex]) { return lowIndex+1; } return lowIndex; } int midIndex = (lowIndex + highIndex + 1)/2; if(key<v2[midIndex]) { return binarySearch(key,midIndex,highIndex); } else { return binarySearch(key,lowIndex,midIndex-1); }}int countTotal(){ int lowIndex = 0; v2.push_back(v1[0]); for(int i=1;i<v1.size();i++) { lowIndex = binarySearch(v1[i],0,v2.size()-1); if(lowIndex>v2.size()-1) { v2.push_back(v1[i]); } else { v2[lowIndex] = v1[i]; } } if(v2[v2.size()-1]==0) { return v2.size()-1; } else { return v2.size(); }}int main(){ int n; cin>>n; for(int i=0;i<n;i++) { int a; cin>>a; v1.push_back(a); } if(n!=0) { cout<<countTotal(); } else{ cout<<n<<endl; } return 0;}