Information
- ID
- 197
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- # Submissions
- 86
- Accepted
- 14
- Uploaded By
你好笨(快请学长喝奶茶)
因为没有平局,所以学长和基友的总分一定是n*(n+1)/2,
所有的情况肯定能通过以下方式构造出一组解,
每次贪心的时候放最大的就行了,
这样的话就只需要判一下是不是这两个数的和s存在一个数n使得n*(n+1)/2=s。(代码里是判断的2s和n(n+1),不会有人看不懂吧)
然后注意一下要开long long。
#include<iostream>
#include<algorithm>
#include<math.h>
const int N=1e5+5;
using namespace std;
typedef long long ll;
ll a,b;
bool fg=0;
int ans[N];
int x,cnt;
int main(){
cin>>a>>b;
ll s=(a+b)*2;
for(ll i=1;i<=sqrt(s);i++){
if(i*(i+1)==s){//判断n*(n+1)/2是否等于s
x=i;
fg=1;
break;
}
}
if(!fg){//没有找到这个数,所以计分结果是错的
cout<<"Wrong";
return 0;
}
cout<<x<<" ";//找到就输出这个数,代表一共进行了这么多轮
for(int i=x;i>=1;i--){//贪心,从大到小开始取
if(!a)
break;
if(a>=i){//取的数存到数组里,直到把a减完
a-=i;
cnt++;
ans[cnt]=i;
}
}
for(int i=cnt;i>=1;i--){
i==1?cout<<ans[i]<<endl:cout<<ans[i]<<" ";
}
return 0;
}
By signing up a 追梦算法网 universal account, you can submit code and join discussions in all online judging services provided by us.