【CF簡介】
提交鏈接：CF 514D
題面：
D. R2D2 and Droid Army time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
An army of n droids is lined up in one row. Each droid is described bym integers a1,?a2,?...,?am, whereai is the number of details of thei-th type in this droid's mechanism. R2-D2 wants to destroy the sequence of consecutive droids of maximum length. He hasm weapons, the i-th weapon can affect all the droids in the army by destroying one detail of thei-th type (if the droid doesn't have details of this type, nothing happens to it).
A droid is considered to be destroyed when all of its details are destroyed. R2-D2 can make at mostk shots. How many shots from the weapon of what type should R2-D2 make to destroy the sequence of consecutive droids of maximum length?
Input
The first line contains three integers n,?m,?k (1?≤?n?≤?105, 1?≤?m?≤?5, 0?≤?k?≤?109) — the number of droids, the number of detail types and the number of available shots, respectively.
Next n lines follow describing the droids. Each line containsm integers a1,?a2,?...,?am (0?≤?ai?≤?108), where ai is the number of details of thei-th type for the respective robot.
Output
Print m space-separated integers, where thei-th number is the number of shots from the weapon of thei-th type that the robot should make to destroy the subsequence of consecutive droids of the maximum length.
If there are multiple optimal solutions, print any of them.
It is not necessary to make exactly k shots, the number of shots can be less.
Examples Input
5?2?4 4?0 1?2 2?1 0?2 1?3
Output
2?2
Input
3?2?4 1?2 1?3 2?2
Output
1?3
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項屬性，每個機器人的每項屬性并不統(tǒng)一。要消滅一個機器人，需要將他的每項屬性值都減為1，現(xiàn)在有k次操作機會，每次操作可以將每個機器人的某項屬性值都減1，問在不超過k次操作的情況下，如何分配每項屬性減幾次，可以使得最終消滅最多的連續(xù)機器人序列，輸出分配攻擊方案。
???? 注意：如果不能全部消滅，則每項輸出0，因為要求消耗盡量少的操作數(shù)，達到殺死盡量多連續(xù)的機器人。
解題：
???? RMQ，區(qū)間詢問問題，可以做到O（nlogn）復雜度預處理，O（log n）復雜度詢問，入門ST算法，可以看這篇博客，通過RMQ預處理好每項屬性，區(qū)間最大值。
???? 隨后詢問時，只要查詢出該區(qū)間每項屬性的最大值，隨后將這些最大值累加，即為消滅該區(qū)間全部機器人的最小操作次數(shù)。
???? 枚舉左端點，二分右區(qū)間，若區(qū)間需要操作數(shù)大于k，則左移右區(qū)間，縮小區(qū)間長度，若小于等于k則，右移右區(qū)間，增大區(qū)間長度。在二分過程中更新區(qū)間最優(yōu)值，同時還需記錄此時的分配情況，若區(qū)間長度相等的情況下，還需保證操作數(shù)盡量小。
代碼：
#include#include#include#include#include#include#include#include#define?LL?long?long
#define?maxn?100010
#define?sq(a)??1LL*(a)*(a)
#define?mod?1000000007
using?namespace?std;
int?arr[maxn][5],d[maxn][5][20],path[5],tmp[5];
int?n,m,k;
void?init()
{
??for(int?i=0;i<n;i++)
??for(int?j=0;j<m;j++)
??d[i][j][0]=arr[i][j];
??for(int?j=1;(1<<j)<=n;j++)
??for(int?i=0;i+(1<<j)-1<n;i++)
??for(int?k=0;k<m;k++)
??d[i][k][j]=max(d[i][k][j-1],d[i+(1<<(j-1))][k][j-1]);
}
int?RMQ(int?le,int?ri)
{
int?k=0,res=0;
for(int?i=0;i<m;i++)
{
k=0;
while((1<<(k+1))<=ri-le+1)
k++;
tmp[i]=max(d[le][i][k],d[ri-(1<<k)+1][i][k]);
res+=tmp[i];
}
return?res;
}
void?update()
{ ?
??for(int?j=0;j<m;j++)
path[j]=tmp[j];
}
int?main()
{
int?le,ri,temp,ans=0,ansk=0x3f3f3f3f;
bool?flag=0;
scanf("%d%d%d",&n,&m,&k);
????for(int?i=0;i<n;i++)
for(int?j=0;j<m;j++)
scanf("%d",&arr[i][j]);
init();
for(int?i=0;i<n;i++)
{
??????le=i;
??????ri=n-1;
??if(ri-le+1<ans)
??break;
??while(le>1;
?temp=RMQ(i,mid);
?if(tempans)
?{
?ansk=temp;
?ans=mid-i+1;
?update();
?}
?else?if(mid-i+1==ans)
?{
?if(ansk>temp)
?{
ansk=temp;
????????????????????update();
?}
?}
?le=mid+1;
?}
?else
?{
?ri=mid-1;
?if(ri-i+1<ans)
?break;
?}
??}
}
printf("%d",path[0]);
for(int?i=1;i<m;i++)
printf("?%d",path[i]);
printf("n");
return?0;
}
下載文檔
