POJ3663

题意简单。

关键：记录每头牛的val值，每次寻找和某头牛匹配的牛时候，可以通过刚刚记录的值来计算。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn = 20005;
 6 const int maxm = 1000005;
 7 int vis[ maxm ],cow[ maxn ];
 8 int main(){
 9     int n,aim;
10     while( scanf("%d%d",&n,&aim)==2 ){
11         memset( vis,0,sizeof( vis ) );
12         for( int i=0;i<n;i++ ){
13             scanf("%d",&cow[i]);
14             vis[ cow[i] ]++;
15         }
16         for( int i=1;i<maxm;i++ ){
17             if( vis[ i ]==0 ) vis[ i ] = vis[ i-1 ];
18             else vis[ i ] = vis[ i-1 ]+vis[ i ];
19         }
20         int ans = 0;
21         for( int i=0;i<n;i++ ){
22             if( aim>=cow[i] ){
23                 ans += vis[ aim-cow[i] ];
24                 if( cow[i]<=aim-cow[i] )
25                     ans--;
26             }
27         }
28         //printf("ans=%d
",ans);
29         ans/=2;
30         printf("%d
",ans);
31     }
32     return 0;
33 }

View Code

对于这里的ans--，是除去牛和本身的组合

keep moving...