场上场下各种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");}
}