P8475 「GLR-R3」雨水 题目思路

题目链接

#include <cstdio> // scanf
#include<stdio.h>
#include<math.h>
const int MAXN = 1e7; // Set a right value according to your solution.
//const double MAX=pow(2,64); 
int n, a[MAXN + 8];
unsigned long long ans;
namespace Generator {

unsigned long long k1, k2;
int thres;

inline unsigned long long xorShift128Plus() {
    unsigned long long k3 = k1, k4 = k2;
    k1 = k4, k3 ^= (k3 << 23), k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

inline void generate() {
    for (int i = 1; i <= n; ++i) {
        a[i] = xorShift128Plus() % thres;
    }
}

} // namespace Generator.
int seach(int beg){//在[beg,end]的区间内寻找最右最小值 
	int remain=1e9,remain_id=0;
	 for(int i=beg;i<=n;i++){
	 	if(a[i]<remain){
	 		remain=a[i];
	 		remain_id=i;
		 }
	 } 
	return remain_id;
}
int seach1(int min,int beg){//beg是这个区间的左区间 
	for(int i=n;i>=beg;i--){
		if(a[i]<=min){
			return i;
		}
	}
} 
void swap(int &a1,int &b1){
	int remain=a1;
	a1=b1;
	b1=remain;
}
int main() {
    scanf("%d", &n);
    scanf("%llu %llu %d", &Generator::k1, &Generator::k2, &Generator::thres);
    Generator::generate();
   
   	int beg=1,end=1;
   	while(beg<=end&&end<=n){
   		//printf("%d %d\n",beg,end);
   	while(a[end]<=a[end+1]&&end+1<=n){
   		end++;
	}
	if(end==n){
		break;
	}
	int end1=0;
	end1=seach(end+1);
	int remain_min=a[end1];
	while(a[beg]<=a[end1]){//关键点1 
		beg++;
	}
	end1=seach1(remain_min,end+1);//关键点2，取最左最小值 
	if(end1){
	swap(a[beg],a[end1]);
	end1++;
	beg=end=end1;}
	
	}
	/* for(int i=1;i<=n;i++){
    	printf("%d ",a[i]);
	}
	printf("\n");*/
	for(int i=1;i<=n;i++){
		unsigned long long remain4=a[i];
		ans+=(remain4*i);
		
	}
	printf("%llu",ans);
    return 0;
}

思路：

本题我使用了双指针来实现寻找到单增区间，beg是单增区间的起点下标，end为结束，然后寻找end+1之后的最左最小值下标end1，如果a[beg]<=a[end1],则向beg下一位寻找需要交换的数。
交换之后，按照题意，新区间的起点为end1+1.
最后注意边界问题即可。