题解 AT3538 【Credits】
rui_er
2019-04-30 16:42:33
# ~~翻译者到此一游~~
## 没看题的回去!!!
这里是C++党领地
> 首先,头文件
```cpp
#include <iostream>
#include <algorithm>
```
> 算法概括
想要上尽量少的课程获得k积分,就把每个课程获得的积分数量从大到小排序。
这里总课程数为n,第i个课程积分数为 $a_i$ 。
```cpp
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
//sth.
sort(a, a+n, cmp);
}
```
从前往后累加,直到获得分数大于等于k。
```cpp
int s = 0;
for(int i=0;i<n;i++)
{
s += a[i];
if(s >= k)
{
cout<<i+1<<endl;
return 0;
}
}
cout<<-1<<endl;
```
最后,完整代码:
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) {return a > b;}
int main()
{
int n, k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
sort(a, a+n, cmp);
int s = 0;
for(int i=0;i<n;i++)
{
s += a[i];
if(s >= k)
{
cout<<i+1<<endl;
return 0;
}
}
cout<<-1<<endl;
return 0;
}
```