最难查出的问题,实际上是思想的盲区。深入地说,也就是对“思想算法”正确性的证明不足。
从这道题中,很容易想到蚯蚓长度在时间轴上具有单调性(粗略想法),以此为切入点。
如果从单调性联想到优先队列,会得到一种“标准”的错误解法,即使用了额外算力保证结果单调性。
事实上,我们已经意识到了蚯蚓存在“潜在的单调性”了。但如果直接将切开产生的新蚯蚓放入队列中,此队列仍是“无序”的。
注意到每次“相对”切割点相同,从这个限制出发,意识到新蚯蚓如果将较长、较短分为两个队列存储,则可分别具备单调性。再附加一个初始队列储存原始蚯蚓,此题即求解完毕。
从这个题目中,我们理解了以“题目限制”为突破口的思想。更广泛地说,我们意识到了预设的“有序”即为我们最根本的依据。
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define int long long
using namespace std;
struct Node;
int getNowLength(Node node,int nowSecond);
const int MAXN=1e5+20;
int second,q;
struct Node{//蚯蚓
int length,//长度
birth;//出生时间
bool operator <(const Node another)const{
return length>another.length;
}
};
queue<Node> origNodes;//初始蚯蚓
queue<Node> newNodes_short;//新蚯蚓 短的
queue<Node> newNodes_long;//新蚯蚓 长的
struct CutResult{//切除结果
int first,second;//两段
};
CutResult cutNode(Node node,int u,int v){//切蚯蚓 u v(p=u/v)
int origLength=node.length;
int newLength1=((origLength)*u/v);
int newLength2=origLength-newLength1;
if(newLength1<newLength2)swap(newLength1,newLength2);
return CutResult{newLength1,newLength2};
}
int u,v;//切开位置参数
int getNowLength(Node node,int nowSecond){
if(((nowSecond-node.birth)*q)<0)return node.length;
return node.length+(nowSecond-node.birth)*q;
}
Node getNowLongestNode(int second){//获取当前最长蚯蚓
Node cutNode;//需要切的蚯蚓
int nowLen=0;//当前最长长度
int biggest=0;//最大的 1:原始 2:long 3:short
Node tmpNode;
if(!origNodes.empty()){//还有老蚯蚓
tmpNode=origNodes.front();
if(getNowLength(tmpNode,second)>nowLen){
nowLen=getNowLength(tmpNode,second);
cutNode=tmpNode;
biggest=1;
}
}
if(!newNodes_short.empty()){
tmpNode=newNodes_short.front();
if(getNowLength(tmpNode,second)>nowLen){
nowLen=getNowLength(tmpNode,second);
cutNode=tmpNode;
biggest=3;
}
}
if(!newNodes_long.empty()){
tmpNode=newNodes_long.front();
if(getNowLength(tmpNode,second)>nowLen){
nowLen=getNowLength(tmpNode,second);
cutNode=tmpNode;
biggest=2;
}
}
switch(biggest){
case 1:
origNodes.pop();
break;
case 2:
newNodes_long.pop();
break;
case 3:
newNodes_short.pop();
break;
}
return cutNode;
}
int t;//输出参数
void outputAll(){//输出所有蚯蚓
int cntt=0;
while(!(newNodes_long.empty()&&newNodes_short.empty()&&origNodes.empty())){
cntt++;
Node longgest=getNowLongestNode(second);
if(!(cntt%t))cout<<getNowLength(longgest,second)<<" ";
}
cout<<endl;
}
Node tmps[MAXN];
signed main(){
int n,//初始蚯蚓数量
m;//秒数
scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);
for(int i=1;i<=n;i++){
int tmp;//长度
scanf("%lld",&tmp);
tmps[i]=Node{tmp,1};
}
sort(tmps+1,tmps+n+1);
for(int i=1;i<=n;i++){
origNodes.push(tmps[i]);
}
//共执行m秒
for(second=1;second<=m;second++){
Node topNode=getNowLongestNode(second);
int nowLength=getNowLength(topNode,second);
topNode.length=nowLength;
CutResult result=cutNode(topNode,u,v);
newNodes_long.push(Node{result.first,second+1});
newNodes_short.push(Node{result.second,second+1});
if(!(second%t))cout<<nowLength<<" ";
}
cout<<endl;
outputAll();
return 0;
}