hdu6396Swordsman 2018杭电多校第七场1011 【优先队列+IO输入优化】

题目链接

题意：

有一个法师 法师身上有k个属性 Vi，     1<=k<=5

  有m只怪物， 每只怪物有k个属性 Aij， 当法师杀死某只怪物的时候， 每一项属性 Vi 可以根据 提高相应的值Bij

m<= 5*1e5

求法师最多可以杀死几只怪物 以及其最终属性是多少

题解：

由于k的值很小，所以我们可以开k个优先队列，每个队列的优先级是从小到大，先将所有怪物加入第一个队列，再将所有小于等于v[i]的怪物pop出来就加入下一个（i+1）队列，即

if（v[i] >= que[i].top）{

     que[i+1].push(que[i].top);

     que[i].pop();

}

循环k遍，如果在第k个队列pop()出来， 就代表该怪物被消灭了， 法师属性更新一遍，再一边遍历一遍每个队列。依次，最后当没有怪物可以被pop出来就说明接下来没有怪物可以被消灭了。

要点：！！！！

输入这里是个坑，一开始用scanf，tle了一发，队友提醒说得输入优化，本来以为这个输入优化很简单，敲了一个read函数，结果发现还是tle，在网上看到别人的AC代码用的是  IO输入输出优化， 才知道有这个东西， 然后copy了dls的优化，有点长QAQ

#include<bits/stdc++.h>
#define ll long long
#define maxn 500005
using namespace std;

namespace IO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
#define ll long long
	//fread->read

	bool IOerror=0;
	inline char nc() {
		static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
		if (p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
			if (pend==p1) {
				IOerror=1;
				return -1;
			}
			//{printf("IO error!\n");system("pause");for (;;);exit(0);}
		}
		return *p1++;
	}
	inline bool blank(char ch) {
		return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
	}
	inline void read(int &x) {
		bool sign=0;
		char ch=nc();
		x=0;
		for (; blank(ch); ch=nc());
		if (IOerror)return;
		if (ch=='-')sign=1,ch=nc();
		for (; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
		if (sign)x=-x;
	}
	inline void read(ll &x) {
		bool sign=0;
		char ch=nc();
		x=0;
		for (; blank(ch); ch=nc());
		if (IOerror)return;
		if (ch=='-')sign=1,ch=nc();
		for (; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
		if (sign)x=-x;
	}
	inline void read(double &x) {
		bool sign=0;
		char ch=nc();
		x=0;
		for (; blank(ch); ch=nc());
		if (IOerror)return;
		if (ch=='-')sign=1,ch=nc();
		for (; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
		if (ch=='.') {
			double tmp=1;
			ch=nc();
			for (; ch>='0'&&ch<='9'; ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
		}
		if (sign)x=-x;
	}
	inline void read(char *s) {
		char ch=nc();
		for (; blank(ch); ch=nc());
		if (IOerror)return;
		for (; !blank(ch)&&!IOerror; ch=nc())*s++=ch;
		*s=0;
	}
	inline void read(char &c) {
		for (c=nc(); blank(c); c=nc());
		if (IOerror) {
			c=-1;
			return;
		}
	}
	//fwrite->write
	struct Ostream_fwrite {
		char *buf,*p1,*pend;
		Ostream_fwrite() {
			buf=new char[BUF_SIZE];
			p1=buf;
			pend=buf+BUF_SIZE;
		}
		void out(char ch) {
			if (p1==pend) {
				fwrite(buf,1,BUF_SIZE,stdout);
				p1=buf;
			}
			*p1++=ch;
		}
		void print(int x) {
			static char s[15],*s1;
			s1=s;
			if (!x)*s1++='0';
			if (x<0)out('-'),x=-x;
			while(x)*s1++=x%10+'0',x/=10;
			while(s1--!=s)out(*s1);
		}
		void println(int x) {
			static char s[15],*s1;
			s1=s;
			if (!x)*s1++='0';
			if (x<0)out('-'),x=-x;
			while(x)*s1++=x%10+'0',x/=10;
			while(s1--!=s)out(*s1);
			out('\n');
		}
		void print(ll x) {
			static char s[25],*s1;
			s1=s;
			if (!x)*s1++='0';
			if (x<0)out('-'),x=-x;
			while(x)*s1++=x%10+'0',x/=10;
			while(s1--!=s)out(*s1);
		}
		void println(ll x) {
			static char s[25],*s1;
			s1=s;
			if (!x)*s1++='0';
			if (x<0)out('-'),x=-x;
			while(x)*s1++=x%10+'0',x/=10;
			while(s1--!=s)out(*s1);
			out('\n');
		}
		void print(double x,int y) {
			static ll mul[]= {1,10,100,1000,10000,100000,1000000,10000000,100000000,
			                  1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
			                  100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL
			                 };
			if (x<-1e-12)out('-'),x=-x;
			x*=mul[y];
			ll x1=(ll)floor(x);
			if (x-floor(x)>=0.5)++x1;
			ll x2=x1/mul[y],x3=x1-x2*mul[y];
			print(x2);
			if (y>0) {
				out('.');
				for (size_t i=1; i<y&&x3*mul[i]<mul[y]; out('0'),++i);
				print(x3);
			}
		}
		void println(double x,int y) {
			print(x,y);
			out('\n');
		}
		void print(char *s) {
			while (*s)out(*s++);
		}
		void println(char *s) {
			while (*s)out(*s++);
			out('\n');
		}
		void flush() {
			if (p1!=buf) {
				fwrite(buf,1,p1-buf,stdout);
				p1=buf;
			}
		}
		~Ostream_fwrite() {
			flush();
		}
	} Ostream;
	inline void print(int x) {
		Ostream.print(x);
	}
	inline void println(int x) {
		Ostream.println(x);
	}
	inline void print(char x) {
		Ostream.out(x);
	}
	inline void println(char x) {
		Ostream.out(x);
		Ostream.out('\n');
	}
	inline void print(ll x) {
		Ostream.print(x);
	}
	inline void println(ll x) {
		Ostream.println(x);
	}
	inline void print(double x,int y) {
		Ostream.print(x,y);
	}
	inline void println(double x,int y) {
		Ostream.println(x,y);
	}
	inline void print(char *s) {
		Ostream.print(s);
	}
	inline void println(char *s) {
		Ostream.println(s);
	}
	inline void println() {
		Ostream.out('\n');
	}
	inline void flush() {
		Ostream.flush();
	}
#undef ll
#undef OUT_SIZE
#undef BUF_SIZE
};
// 以上为输入输出优化



int v[5+1], a[5+1][maxn], b[5+1][maxn];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >que[5+1];
int main() {
	int t;
	cin>>t;
	while(t--) {
		int k, m;
		IO::read(m);
		IO::read(k);
		for(int i = 0; i < k; i++) {
			IO::read(v[i]);
			while(!que[i].empty()) {
				que[i].pop();
			}
		}
		for(int j = 0; j < m; j++) {
			for(int i = 0; i < k; i++) {
				IO::read(a[i][j]);
			}
			for(int i = 0; i < k; i++) {
				IO::read(b[i][j]);
			}
		}
		for(int i = 0; i < m; i++) {
			que[0].push(make_pair(a[0][i], i));
		}
		bool ok = false;
		int ans = 0;
		while(!ok) {
			ok = true;
			for(int i = 0; i < k; i++) {
				while(!que[i].empty()) {
					int value = que[i].top().first;
					int id = que[i].top().second;
					if(v[i] < value) {
						break;
					}
					if(i == k-1) {
						ok = false;
						ans++;
						que[i].pop();
						for(int j = 0; j < k ; j++) {
							v[j] += b[j][id];
						}
					} else {
						que[i].pop();
						que[i+1].push(make_pair(a[i+1][id], id));
					}
				}
			}
		}
		printf("%d\n",ans);
		printf("%d",v[0]);
		for(int i = 1; i < k; i++) {
			printf(" %d",v[i]);
		}
		printf("\n");
	}
	return 0;
}