jzoj 1570. 【普及模拟】射击

发布于 2019-03-19  21 次阅读


 

题目描述

射击规则如下:

你最多可以射击4次,当然你也可以不射击,目标靶被分成N部分,每一部分的分值为P1,….,PN,你的总分为每次射击的分数之和,如果S不超过M,那你的分数就是S;否则如果S超过M,那么你的分数变为0。

写一个程序,给你每部分的分值以及M的值,计算你能得到的最大得分。

 

输入

   输入第一行是两个空格隔开的整数N(1<=N<=1000)和M(1<=M<=200000000=2*10^8),接下来N行每行一个整数Pi(1<=Pi<=100000000=10^8)。

输出

    输出一个整数表示你的最大得分。
先把每两个加起来,然后用两个指针来找,如果大于m,j-1不然i+1;一直到i>J

 

#include
#include
using namespace std;
int a[100000],b[1000000];
int main()
{
	freopen("dart1.in","r",stdin);
	freopen("dart.out","w",stdout);
	int i,j,n,m,s,x,y;
	int max,k;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
	scanf("%d",&a[i]);
	max=0;
	k=1;
	for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
	{
		b[k]=a[i]+a[j];
		k++;
	}	
	sort(b,b+k);	
	k--;
	i=1; j=k;
	while (i<=j)
	{
        if (b[i]+b[j]>m) j--;
        else 
		{
        	if (b[i]+b[j]>max) max=b[i]+b[j];
        	i++;
        }
	}
	printf("%d",max);	
	return 0;
}

 

]]>


「墨泼三千烟火,许你一世迷离」