PAT甲级1048.

目录

A1048

题目

样例

样例1

输入:

8 15
1 2 8 7 2 4 11 15

输出:

4 11

样例2

输入:

7 14
1 8 7 2 4 11 15

输出:

No Solution

思路和坑点

　　使用两点法，把币值从小到大排序，然后头尾各一个指针向中间逼近，如果有答案则输出，否则按照要求输出无解。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n,m;
    scanf("%d%d",&n,&m);
    vector<int> v(n);
    for(int i=0;i<n;i++)
        scanf("%d",&v[i]);
    sort(v.begin(),v.end());
    int i=0,j=n-1,flag=0;                //两点法，i，j为两端的指针，flag为答案的标记 
    while(i<j){
        int sum=v[i]+v[j];
        if(sum<m)    i++;
        else if(sum==m){
            printf("%d %d",v[i],v[j]);
            flag=1;    break;
        }
        else    j--;
    } 
    if(flag==0) puts("No Solution");
    return 0;
}