Note
In the first test the second, third and fourth droids will be destroyed.
In the second test the first and second droids will be destroyed.
题意:有n个机器人，每个机器人有m种部件组成，每种部件可以有多个，有m种抢，每种抢发射一次能是所有机器人对应的部件减1，总共不得发射超过k次，求在伤害机器人数目最大（机器人要求连续）的情况下每种抢发射的最少次数。
思路：线段树+二分，线段树用来求区间最大值，先二分出答案（连续伤害的机器人数），然后枚举起点，知道起点，，有范围就知道了终点，然后求这范围内需要设计的最大数目看满不满足条件
注意：如果你的线段树的水平写不了叉姐的水准，乖乖的将结点开3~4万吧，开2万的话会RE。。。因为这TM我的水平写线段树写不了最完美的二叉树(mb)
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>using namespace std;const int MAXNODE = 400000+1000;const int MAX = 1000003;struct NODE{int value[6];// 结点对应区间的权值int left,right; // 区间 [left,right]} node[MAXNODE];int father[MAX];// 每个点(当区间长度为0时，对应一个点)对应的结构体数组下标int a[MAXNODE][6];int n,m,k;int temp[6],ans[6];void BuildTree(int rt,int left,int right){node[rt].left = left;node[rt].right = right;if (left == right){for(int i = 1; i <= m; i++ ){node[rt].value[i] = a[left][i];}return;}int mid = (right+left)/2;BuildTree(rt<<1, left, mid );BuildTree(rt<<1|1, mid + 1, right);for(int i = 1; i <= m; i++){node[rt].value[i] = max(node[rt<<1].value[i], node[rt<<1|1].value[i]);}}int Query(int i,int l,int r,int x) // i为区间的序号（对应的区间是最大范围的那个区间，也是第一个图最顶端的区间，一般初始是 1 啦）{if (l== node[i].left && node[i].right == r) // 找到了一个完全重合的区间{return node[i].value[x];}int Max = 0;i = i << 1; // get the left child of the tree nodeif (l <= node[i].right) // 左区间有涉及{if (r <= node[i].right) // 全包含于左区间，则查询区间形态不变Max = Query(i, l, r,x);else // 半包含于左区间，则查询区间拆分，左端点不变，右端点变为左孩子的右区间端点Max =Query(i,l, node[i].right,x);}i += 1; // right child of the treeif (r >= node[i].left) // 右区间有涉及{if (l >= node[i].left) // 全包含于右区间，则查询区间形态不变Max =max(Max, Query(i, l, r,x));else // 半包含于左区间，则查询区间拆分，与上同理Max =max(Max, Query(i, node[i].left, r,x));}return Max;}bool ok(int mid){bool flag = false;for(int i = 1; i <= n – mid+1; i++){int num = 0;//cout<<"i = "<<i;for(int j = 1; j <= m; j++){temp[j] = Query(1,i, i+mid-1 , j);num += temp[j];//cout<<temp[j]<<" ";}// cout<<endl;if(num <= k){flag = true;memcpy(ans,temp,sizeof(temp));// cout<<i<<" "<<ans[1]<<" "<<ans[2]<<endl;break;}fill(temp,temp+6,0);}if(flag) return true;else return false;}void solve(){int left = 1, right = n;while(left <= right){int mid = (left + right)/2;// cout<<mid<<endl;if(ok(mid)){left = mid + 1;}else right = mid – 1;}printf("%d",ans[1]);for(int i = 2; i <= m; i++) printf("% d",ans[i]);printf("\n");}int main(){#ifdef xxzfreopen("in.txt","r",stdin);#endif // xxzwhile(scanf("%d%d%d",&n,&m,&k) != EOF){for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)scanf("%d",&a[i][j]);BuildTree(1,1,n);solve();}return 0;}
伟人之所以伟大，是因为他与别人共处逆境时，
