題目描述

又到了豐收的季節(jié)，恰逢小易去牛牛的果園里游玩。
牛牛常說他對(duì)整個(gè)果園的每個(gè)地方都了如指掌，小易不太相信，所以他想考考牛牛。
在果園里有N堆蘋果，每堆蘋果的數(shù)量為ai，小易希望知道從左往右數(shù)第x個(gè)蘋果是屬于哪一堆的。
牛牛覺得這個(gè)問題太簡(jiǎn)單，所以希望你來替他回答。

輸入描述:

第一行一個(gè)數(shù)n(1 <= n <= 105)。 第二行n個(gè)數(shù)ai(1 <= ai?<= 1000)，表示從左往右數(shù)第i堆有多少蘋果 第三行一個(gè)數(shù)m(1 <= m <= 105)，表示有m次詢問。 第四行m個(gè)數(shù)qi，表示小易希望知道第qi個(gè)蘋果屬于哪一堆。

輸出描述:

m行，第i行輸出第qi個(gè)蘋果屬于哪一堆。

示例1

輸入

復(fù)制

5 2 7 3 4 9 3 1 25 11

輸出

復(fù)制

1 5 3

先將要輸入的多組詢問排序，之后從頭開始遍歷蘋果堆，如果連數(shù)值較小的詢問當(dāng)前都無法滿足，那么大的詢問自然無法滿足

之后再將詢問恢復(fù)之前的次序輸出即可

#include<stdio.h>
#include<iostream>
#include <algorithm>
using namespace std;
typedef struct Test1
{
?? ?int Num; ? //記錄各次詢問的值?
?? ?int No; ? ?//記錄各詢問一開始的序號(hào)，方便最后恢復(fù)次序?
?? ?int flag; ?//記錄屬于第幾堆?
}Test;
bool cmp1(Test x,Test y)
{
?? ?return x.Num<y.Num;
}
bool cmp2(Test x,Test y)
{
?? ?return x.No<y.No;
}
int main()
{
?? ?int n,m,i,sum=0,j;
?? ?scanf("%d",&n);
?? ?int a[n];
?? ?for(i=0;i<n;i++)
?? ?{
?? ??? ?scanf("%d",&a[i]);
?? ?}
?? ?scanf("%d",&m);
?? ?Test b[m];
?? ?for(i=0;i<m;i++)
?? ?{
?? ??? ?scanf("%d",&b[i].Num);
?? ??? ?b[i].No=i;
?? ?}
?? ?sort(b,b+m,cmp1);
?? ?j=0;
?? ?sum=a[0];
?? ?for(i=0;i<m;)
?? ?{
?? ??? ?if(b[i].Num<=sum)
?? ??? ?{
?? ??? ??? ?b[i].flag=j;
?? ??? ??? ?i++;
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?j=j+1;
?? ??? ??? ?sum+=a[j];
?? ??? ?}
?? ?}
?? ?sort(b,b+m,cmp2);
?? ?for(i=0;i<m;i++)
?? ?{
?? ??? ?printf("%d\n",b[i].flag+1);
?? ?}
}

總結(jié)

以上是生活随笔為你收集整理的牛客网--2019校招--丰收的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。