NC16040. 分数
描述
输入描述
第一行四个正整数n,m,k,C (m <= 6, k <= n <= 500, C <= 500)。
接下来一行m个整数w1, w2, ..., wm，表示每场比赛的权重，第i场比赛的权重为wi/(w1+w2+...+wm)，保证wi >= 0且1 <= w1 + w2 + ... + wm <= 1000。
接下来n行每行m个整数，第i个整数表示这个选手在第i场比赛中获得的成绩。如果这个数字为-1表示这个数据丢失，保证恰好有一个-1。
输出描述
n行每行输出一个1到3之间的整数。1表示一定出线，2表示一定不出线，3表示可能出线。
示例1
输入:
4 2 2 100 1 1 100 99 70 70 40 -1 100 39
输出:
1 3 3 2
C++11(clang++ 3.9) 解法, 执行用时: 13ms, 内存消耗: 496K, 提交时间: 2020-02-15 21:17:02
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
typedef unsigned long long score;
const int N=510;
int n,m,k,c,w[N],sco[N][10],sx,sy,ms[10],c1[N],c2[N];
score wt[N],s[N],t[N];
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&c);
for(int i=0;i<m;i++)
{
scanf("%d",w+i);
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&sco[i][j]);
if(sco[i][j]==-1)
{
sx=i;
sy=j;
}
}
}
for(int x=0;x<c+1;x++)
{
sco[sx][sy]=x;
for(int j=0;j<m;j++)
{
ms[j]=0;
for(int i=0;i<n;i++)
{
ms[j]=max(ms[j],sco[i][j]);
}
}
for(int j=0;j<m;j++)
{
wt[j]=w[j];
if(ms[j]==0)
{
wt[j]=0;
continue;
}
for(int k=0;k<m;k++)
{
if(j!=k&&ms[k]!=0)
wt[j]*=ms[k];
}
}
for(int i=0;i<n;i++)
{
s[i]=0;
for(int j=0;j<m;j++)
{
s[i]+=wt[j]*sco[i][j];
}
t[i]=s[i];
}
sort(s,s+n);
reverse(s,s+n);
for(int i=0;i<n;i++)
{
if(t[i]>=s[k-1]) c1[i]++;
if((k!=n)&&t[i]<=s[k]) c2[i]++;
}
}
for(int i=0;i<n;i++)
{
if(c2[i]==0) puts("1");
else if(c1[i]==0) puts("2");
else puts("3");
}
return 0;
}