场上场下各种TLE到怀疑人生。。。经过大佬指点之后才知道要用fread才能过,一般的快读不行。。。
题意:一个剑客打小怪兽,有n头小怪兽,剑客和小怪兽有m个属性。只有剑客的m个属性都大于等于某个小怪兽的属性,才能击杀这个小怪兽(即属性全方位碾压才能击杀),每击杀一个小怪兽可以获得属性的加成,问最终击杀的小怪兽数量和最终的属性值。
思路:最终可以击杀的数量与击杀顺序无关(因为能击杀的早晚都会击杀),可以对小怪兽的m个属性排序,从小往大扫描,到剑客的该属性值停止,记录小怪兽出现的次数。如果某个小怪兽出现了m次,说明可以击杀,放入队列。每次循环开始时加上击杀小怪兽的增幅效果,队列为空时为最终答案。
fread! fread! fread! 重要的事情说3遍。
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
typedef long long ll;
pair<int,int> b[6][maxn];
int a[6],c[6][maxn],n,m,s[6],cnt[maxn];
int pos,len;
char buf[1005]; int xchar()
{
if (pos == len)
pos = 0, len = fread(buf, 1, 1005, stdin);
return buf[pos++];
} int readint()
{
int x=0,s=1,c=xchar();
while (c <= 32)
c = xchar();
if (c == '-')
s = -1, c = xchar();
for (; isdigit(c); c = xchar())
x = x*10+c-'0';
return x*s;
} void add(int pos){
for(int i=1;i<=m;i++)
a[i]+=c[i][pos];
}
queue<int> q;
int main(){
// freopen("1.txt","r",stdin);
int T,ans=0;
// scanf("%d",&T);
T=readint();
while(T--){
ans=0;
memset(cnt,0,sizeof(cnt));
// scanf("%d%d",&n,&m);
n=readint(),m=readint();
for(int i=1;i<=m;i++){
a[i]=readint();
}
// scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
// scanf("%d",&b[j][i].first);
b[j][i].first=readint();
b[j][i].second=i;
}
for(int j=1;j<=m;j++){
// scanf("%d",&c[j][i]);
c[j][i]=readint();
}
}
for(int i=1;i<=m;i++)
sort(b[i]+1,b[i]+1+n);
for(int i=1;i<=m;i++){
s[i]=1;
}
for(int i=1,j;i<=m;i++){
for(j=s[i];b[i][j].first<=a[i]&&j<=n;j++){
cnt[b[i][j].second]++;
if(cnt[b[i][j].second]==m)
q.push(b[i][j].second);
}
s[i]=j;
}
while(!q.empty()){
add(q.front());
q.pop();
ans++;
for(int i=1,j;i<=m;i++){
for(j=s[i];b[i][j].first<=a[i]&&j<=n;j++){
cnt[b[i][j].second]++;
if(cnt[b[i][j].second]==m)
q.push(b[i][j].second);
}
s[i]=j;
}
}
printf("%d\n%d",ans,a[1]);
for(int i=2;i<=m;i++)
printf(" %d",a[i]);
printf("\n");
}
}