题面:
【题目描述】
诗诗是一个不擅长数学的女孩子,她的数学试卷红叉遍布。
但是她长于语文,尤善活用成语。她想到了"石沉大海"一词,深得启发,于是决定用石头压住数学试卷,沉入海底,以免被别人看到。
诗诗的试卷可以承载w重量的石头,也就是说,如果用恰好w重量的石头压住试卷,试卷犹可浮于水面,超过w重量则会沉入海底。
诗诗有n块石头,她想知道她至少需要多少块石头才能完成"石沉大海"的大业。
题目保证n块石头总重量大于w。
【输入格式】
第1行,两个正整数w,n,分别表示试卷可以承载的重量和诗诗所持的石头个数。
之后n行,每行1个正整数,依次表示n块石头的重量。
【输出格式】
1行,一个正整数,至少需要使用的石头块数。
【输入样例#1】
666 6
100
8
16
500
50
10
【输出样例#1】
5
【输入样例#2】
63878 10
8740
6801
7835
271
8080
7599
8000
9877
1224
6947
【输出样例#2】
8
【数据范围】
对60%的数据:n≤10000;
对100%的数据:1≤w≤10
9
;
10≤n≤5000000;
1≤ 每块石头的重量 ≤10000;
我的程序(8AC 1WA 1TLE)
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
int ans,stone,paper,s[5000050];
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
cin>>paper>>stone;
for(int i=0;i<stone;i++)scanf("%d",&s[i]);
sort(s+0,s+stone,cmp);
for(int i=0;i<stone;i++)
{
if(ans>=paper){printf("%d",i);return 0;}
else ans+=s[i];
}
return 0;
}
球找错。