NC26141. Fate Grand Order
描述
输入描述
第1行有2个整数n, m，圣晶石数量和活动数量（0<= n <=6000, 1<= m <=2000）；
第2行有m个小数，表示每个活动角色的抽取概率p（0 <= p <= 1）；
第3行有m个整数，表示每个活动角色抽到的话trx可获得的开心值x（0 <= x <= 10000）。
输出描述
输出1行长度为m的01串，表示抽卡计划，其中0表示不抽，1表示抽。
示例1
输入:
3 5 0.1 0.05 0.03 0.0001 0.9 100 100 100 100 100
输出:
00001
C++(g++ 7.5.0) 解法, 执行用时: 6ms, 内存消耗: 480K, 提交时间: 2023-04-14 23:01:46
#include<bits/stdc++.h>
#define xs first
#define ys second
using namespace std;
typedef pair<double,int> PDI;
const int N=6010;
int dp[N];
PDI e[N];
int n,m;
int ans[N];
signed main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>e[i].xs;
for(int i=1;i<=m;i++)
{
int t;
cin>>t;
e[i].xs*=t;
e[i].ys=i;
}
sort(e+1,e+m+1,greater<PDI>());
for(int i=1;i<=(int)min(n/3,m);i++)
ans[e[i].ys]=1;//,cout<<e[i].ys;
for(int i=1;i<=m;i++)cout<<ans[i];
}
C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 504K, 提交时间: 2020-02-17 15:22:46
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#include<algorithm>
using namespace std;
int n,m,x,r[2100];
double p[2100];
bool b[2100];
inline bool cmp(int a,int b)
{
return p[a]>p[b];
}
int main()
{
scanf("%d%d",&m,&n);
m/=3;
fo(i,1,n) scanf("%lf",&p[i]);
fo(i,1,n)
{
scanf("%d",&x);
p[i]*=x;
r[i]=i;
}
sort(r+1,r+n+1,cmp);
fo(i,1,m) b[r[i]]=1;
fo(i,1,n) putchar('0'+b[i]);
return 0;
}
C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 500K, 提交时间: 2019-06-08 13:13:28
#include<stdio.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#include<algorithm>
using namespace std;
int n,m,x,r[2100];
double p[2100];
bool b[2100];
inline bool cmp(int a,int b){
return p[a]>p[b];
}
int main(){
scanf("%d%d",&m,&n);
m/=3;
fo(i,1,n) scanf("%lf",&p[i]);
fo(i,1,n){
scanf("%d",&x);
p[i]*=x;
r[i]=i;
}
sort(r+1,r+n+1,cmp);
fo(i,1,m) b[r[i]]=1;
fo(i,1,n) putchar('0'+b[i]);
return 0;
}