jzoj 1570. 【普及模拟】射击

lzusa 发布于 2019-03-20 1 次阅读

题目描述

射击规则如下：

你最多可以射击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<stdio.h>
#include<algorithm>
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;
}