链家的垃圾OJ系统

// Lianjia01.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <map>
#include <queue>
#include <set>
#include <iterator>
#include <algorithm>
using namespace std;

int findk(int * arrS, int * arrE, int low, int high, int key) 
{
 if (low > high)
  return -1;
 int mid = low + (high - low) / 2;
 if (key >= arrS[mid] && key <= arrE[mid])return mid+1;
 else if (key >= arrE[mid])return findk(arrS, arrE, mid + 1, high, key);
 else return findk(arrS, arrE, low, mid - 1, key);
}

 int main()
{
 ifstream fin("file.txt");
 int n;
 fin >> n;
 int * arr = new int[n];
 for (int i = 0;i < n;++i)fin >> arr[i];
 
 int * arrS = new int[n];
 int * arrE = new int[n];
 arrS[0] = 1;
 arrE[0] = arr[0];
 int sum = 0;
 for (int i = 0;i < n-1;++i)
 {
  sum += arr[i];
  arrS[i+1] = sum + 1;
  arrE[i] = sum;
 }
 sum += arr[n - 1];
 arrE[n - 1] = sum;

 /*for (int i = 0;i < n;++i)
 cout << arrS[i] << "   " << arrE[i] << endl;*/

 int q;
 fin >> q;
 int query;
 for (int i = 0;i < q;++i)
 {
  fin >> query;
  cout << findk(arrS, arrE, 0, n, query) << endl;
 }

 return 0;
}