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;
}
页:
[1]