反恐精英

反恐精英

时间: 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);

    }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注