acwing——800. 配列要素のターゲットと
10017 ワード
800.配列要素のターゲットと
2つの昇順ソートの秩序配列AおよびBと、1つの目標値xが与えられる.配列の下付き文字は0から始まります.A[i]+B[j]=xを満たす数対(i,j)を求めてください.
データは一意の解を保証します.
入力フォーマットの最初の行は、Aの長さ、Bの長さ、およびターゲット値xを表す3つの整数n、m、xを含む.
2行目は、配列Aを表すn個の整数を含む.
3行目は、配列Bを表すm個の整数を含む.
出力フォーマットは、2つの整数iとjを含む1行です.
データ範囲配列の長さは100000を超えない.同じ配列内の要素はそれぞれ異なります.1≦配列要素≦109入力サンプル:4 5 6 1 2 4 7 4 6 8 9出力サンプル:1
問題を解く構想1:
暴力的なやり方.
プログラムコード1:
問題を解く考え方2:
ダブルポインタアルゴリズム
プログラムコード2:
2つの昇順ソートの秩序配列AおよびBと、1つの目標値xが与えられる.配列の下付き文字は0から始まります.A[i]+B[j]=xを満たす数対(i,j)を求めてください.
データは一意の解を保証します.
入力フォーマットの最初の行は、Aの長さ、Bの長さ、およびターゲット値xを表す3つの整数n、m、xを含む.
2行目は、配列Aを表すn個の整数を含む.
3行目は、配列Bを表すm個の整数を含む.
出力フォーマットは、2つの整数iとjを含む1行です.
データ範囲配列の長さは100000を超えない.同じ配列内の要素はそれぞれ異なります.1≦配列要素≦109入力サンプル:4 5 6 1 2 4 7 4 6 8 9出力サンプル:1
問題を解く構想1:
暴力的なやり方.
プログラムコード1:
#include
using namespace std;
const int N=100010;
int a[N],b[N];
int main()
{
int n,m,x;
cin>>n>>m>>x;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<m;i++) cin>>b[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(a[i]+b[j] == x)
{
cout<<i<<" "<<j<<endl;
return 0;
}
}
}
return 0;
}
問題を解く考え方2:
ダブルポインタアルゴリズム
プログラムコード2:
#include
using namespace std;
const int N = 100010;
int n,m,x;
int a[N],b[N];
int main()
{
scanf("%d%d%d",&n,&m,&x);
for (int i=0;i<n;i++) cin>>a[i];
for (int i=0;i<m;i++) cin>>b[i];
for (int i=0,j=m-1;i<n;i++)
{
while (j>=0 && a[i]+b[j] > x)
j--;
if (a[i]+b[j] == x)
{
cout<<i<<' '<<j<<endl;
break;
}
}
return 0;
}
}