【PAT甲级真题】- Find Coins (25)

题目来源

Find Coins (25)

题目描述点击链接自行查看

注意点：

• 多个例子输出最小的那个

思路简介

很简单的双指针 先排序，然后从两头往中间遍历 如果硬币值大就左移右指针（减小数值），否则右移左指针（增加数值） 搜到就直接输出，到最后还没有符合条件的样例输出 "No Solution"

25分真的比20分好拿吧。。。没有奇奇怪怪的模拟难

遇到的问题

代码

/**
* https://www.nowcoder.com/pat/5/problem/4087
* 双指针
*/
#include<bits/stdc++.h>
using namespace std;

void solve(){
int n,v;
cin>>n>>v;
vector<int>num(n);
for(int i=0;i<n;++i)cin>>num[i];
sort(num.begin(),num.end());
int l=0,r=n–1;
while(l<r){
int tmp=num[l]+num[r];
if(tmp>v)r—;
if(tmp<v)l++;
if(tmp==v){
cout<<num[l]<<' '<<num[r];
return;
}
}
cout<<"No Solution";
}

int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//fstream in("in.txt",ios::in);cin.rdbuf(in.rdbuf());
int T=1;
//cin>>T;
while(T—){
solve();
}
return 0;
}