C/C++第五十一次程序大赛

明次

C/C++第五十一次程序大赛题目：训练场上n(1≤n≤50000)个高矮都不相同的士兵从左到右排成一行，依次编号为1，2，…，n。第i个士兵的身高H(i)，由于采用特殊单位，H(i)满足1≤H(i)≤2000000000。设第i个士兵右侧最近的比他个高的士兵编号为j，则第i个士兵可看到在他的右侧比他矮的士兵的个数S(i)=j-i-1。（不考虑客观因素，比如视力范围等-,-）
求S(1)+S(2)+…+S(n)。
输入：
标准输入。
第一行为整数n，表示士兵的个数。
第二行n个整数，用一个空格隔开。分别表示编号为1,2。。。n的士兵的身高
输出：
S(1)+S(2)+…+S(n)的结果
例：
输入
6
10 3 7 4 12 2
输出
5
例子说明：
S(1) = 3
S(2) = 0
S(3) = 1
S(4) = 0
S(5) = 1
S(6) = 0
S(1)+S(2)+S(3)+S(4)+S(5)+S(6) = 3+0+1+0+1+0 = 5


解答：
#include<iostream>
#include<vector>
using namespace std;
bool InputData(const std::size_t &n,vector<std::size_t> &vec);//input n datas
vector<std::size_t>::const_iterator find_iff(vector<std::size_t>::const_iterator&,
            vector<std::size_t>::const_iterator&,
            const std::size_t &value);
//find a >value data in vec from begin to end
//return the first iterator of the value ,no exits return 0;
std::size_t CouterS(const vector<std::size_t>&);
//Counter S(i)
int main(int argc,char** argv)
{
std::size_t n;//input n datas
vector<std::size_t> vec;
cout<<"Input a integer n:"<<endl;
cin>>n;
InputData(n,vec);//input n datas
cout<<CouterS(vec)<<endl;//output result
return 0;
}
bool InputData(const std::size_t &n,vector<std::size_t> &vec)
{//input n datas
std::size_t i=0;
cout<<"Input "<<n<<" datas"<<endl;
  while(i<n)
  {
   std::size_t input;
   cin>>input;
   vec.push_back(input);
   i++;
  }
  return true;
}
vector<std::size_t>::const_iterator find_iff(vector<std::size_t>::const_iterator &begin,
            vector<std::size_t>::const_iterator &end,
            const std::size_t &value)
{
//find a >value data in vec from begin to end
//return the first iterator of the value ,no exits return 0
for(vector<std::size_t>::const_iterator it=begin;it!=end;it++)
{
  if(*it>value) return it;
}
return 0;
}
std::size_t CouterS(const vector<std::size_t> &vec)
{
//Counter S(i)
std::size_t result=0;
    vector<std::size_t>::const_iterator j;
for(vector<std::size_t>::const_iterator it=vec.begin();it!=vec.end();it++)
{  
  vector<std::size_t>::const_iterator begin=it;
   j=find_iff(begin,vec.end(),*begin);
   //find the corresponsing data
   if(j!=0)
            result+=j-it-1;
  }
return result;
}