反恐精英
时间： 1ms 内存：128M
描述：
17125 部队有N 名战士， 依次编号为1,2,3 … N, 每名战士对应一个战斗力P(0<=P<=100)。为维持该部队的正常运转，规定每次只能派出连续编号的若干个战士完成指定任务。两会期间，反动势力聚集在郊区，试图制造恐怖事件。为维护两会的正常开展，总司令命令17125 部队歼灭该伙恐怖分子。已知派出战士战斗力的总和需大于等于恐怖分子的总战斗力M 才可将其歼灭，为便于潜入敌人内部，总司令决定派遣最少数量的战士来完成此次任务，请你帮总司令决定至少派遣多少名战士才能完成此次任务。（假设所有战士均可参与此次任务）
输入：
第一行给出整数T(1<=T<=10) ， 表示有T 组数据。每组数据第一行两个整数N(1<=N<=100000）表示有N 名战士，M(0<M<100000)表示消灭敌人的战斗力下限，第二行给出N 个整数，第i 个数代表标号为i 的战士的战斗力Pi(0<Pi<100)。
输出：
对于每组测试数据，单行输出完成此任务至少需要的战士数。若此任务无法完成，输出-1。
示例输入：
3
10 20
8 2 1 13 2 5 9 6 3 4
6 30
8 2 1 5 3 4
2 5
3 2示例输出：
3
-1
2
提示：
参考答案（内存最优[1068]）：
#include<stdio.h>
int main(){
int t, m,a[100005],ans,i,j,flag;
int sum,max;
scanf("%d",&t);
while(t--){
flag=0;
scanf("%d %d",&m,&max);
sum=0;
for(i=0;i<m;i++){
scanf("%d",&a[i]);
if(a[i]>=max)
flag =1;
sum+=a[i];
}
if(flag)
printf("1\n");
else
if(sum<max)
printf("-1\n");
else{
ans=m;
for(i=0;i<m;i++){
sum=0;
for(j=i;j<m;j++){
sum+=a[j];
if(sum>=max){
if(ans>j-i)
ans=j-i;
break;
}
}
if(sum<max)
break;
}
printf("%d\n",ans+1);
}
}
return 0;
}参考答案（时间最优[20]）：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
int data[100000];
int res=0,pop,i,j,test;
scanf("%d",&n);
while(n--)
{
res = 0;
scanf("%d%d",&pop,&test);
for(i=0;i<pop;i++)
{
scanf("%d",&data[i]);
}
int m = 0;
int n = 1;
int sum = data[0]+data[1];
int min = 100000;
while(n<pop&&n>m)
{
if(sum<test)
{
n++;
sum+=data[n];
}
else
{
if(min>n-m+1)
min = n-m+1;
sum-=data[m];
m++;
}
}
if(min!=100000)
printf("%d\n",min);
else
printf("-1\n",min);
}
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。