首页 > 代码库 > CSUOJ 1343

CSUOJ 1343

1343: Long Long

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 180  Solved: 48
[Submit][Status][Web Board]

Description

    现在有两个单调递增序列,第一个序列有N个整数,第二个序列有M个整数,现在你可以从第一个序列中选一个数x,然后从第二个序列中选一个数y,那么有多少种情况满足x+y<=K呢?

Input

    输入包含多组数据。
    对于每组测试数据,第一行包含两个整数NM , K (1 <= NM <= 105, 1 <= K <= 109),含义同上。接下来一行包含N个在[1, 109]范围内的整数,依次描述了第一个序列中的各个整数。再接下来一行包含M个在[1, 109]范围内的整数,依次描述了第二个序列中的各个整数。

Output

    对于每组数据,输出有多少种情况满足x + y <= K

Sample Input

2 3 53 73 5 74 5 61 2 3 41 2 3 4 54 5 91 2 3 41 2 3 4 5

Sample Output

0

简单二分
注意用long long来存

#include <iostream>
using namespace std;


int main()
{
  int N,M,K;
  while(cin>>N>>M>>K)
  {
  int* First = new int[N+1];
  for(int i = 1;i<N+1;i++)
  {
    cin>>First[i];
  }

  int* Second = new int[M+1];
  for(int j = 1;j<M+1;j++)
  {
    cin>>Second[j];
  }

  long long ans = 0;
  for(int i =1;i<N+1;i++)
  {

  int temp =0;
  if(First[i]+Second[1]>K)
  {
  }else if(First[i]+Second[M]<=K)
  {
  ans+=M;
  }else{
  int high = M;
  int low = 1;
  while(high-low>0)
  {
    int mid = (high+low)/2;
    if(First[i]+Second[mid]>K)
    {
      high = mid - 1;
    }else
    {
      low = mid +1;
    }
  }
  temp = (high+low)/2;
  if((First[i]+Second[temp]<=K))
  {
    ans+=temp;
  }else
  {
  ans+=temp-1;
  }
  }
  }

cout<<ans<<endl;

}
return 0;
}