Coderforces Rockethon 2014 Trial Contest: Testing Round #10 A2. Skis

发布时间:2014-10-22 18:09:57编辑 分享查询网我要评论
本篇文章主要介绍了"Coderforces Rockethon 2014 Trial Contest: Testing Round #10 A2. Skis",主要涉及到Coderforces Rockethon 2014 Trial Contest: Testing Round #10 A2. Skis方面的内容,对于Coderforces Rockethon 2014 Trial Contest: Testing Round #10 A2. Skis感兴趣的同学可以参考一下。

A2. Skis time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output A warehouse of the oldest sports shop of Berland received n skis, the length of the i-th ski equals ai centimeters. Your task is to find out the largest number of ski packs to sell if a ski pack must contain two skis and the sum of their lengths must equal exactly q centimeters. Note that the Berland skis aren't differentiated as left or right. Input The first line contains two positive integers n and q. The second line contains n positive integers a1, a2, ..., an (1 ≤ ai ≤ q). Limits n and q are distinct for distinct problems: for subproblem A1: 1 ≤ n, q ≤ 100, for subproblem A2: 1 ≤ n, q ≤ 106. Output Print the required maximum number of packs. Sample test(s) input 7 51 2 1 4 3 1 3 output 2 n个数,求和为q的对数 统计每个数xi出现的次数记为a[x],取min(a[x],a[q-x]),求和即可,注意当x+x=q时特判 #include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<ctime> #include<cctype> #include<cmath> #include<string> #include<cstring> #include<queue> #include<vector> #define sqr(x) (x)*(x) #define INF 0x1f1f1f1f #define PI 3.1415926535 #define mm 1000001 using namespace std; int a[mm],n,q,x,cnt; int main() { scanf("%d%d",&n,&q); memset(a,0,sizeof(a)); for (int i=0;i<n;i++) { scanf("%d",&x); a[x]++; } cnt=0; for (int i=0;i<q;i++) //这里到q/2就可以了 { if (q%2==0 && i==q>>1) { cnt+=(a[i]>>1); a[i]=0; continue; } cnt+=min(a[i],a[q-i]); a[i]=a[q-i]=0; } printf("%d\n",cnt); return 0; }

上一篇:【简单题】-CF-390B-Inna, Dima and Song