Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

暴力超时了/(ㄒoㄒ)/~~

Posted by 20223465 at 2024-04-10 17:37:08 on Problem 2452
#include<iostream>


#define MAXN  50001
using namespace std;
//找出每个数i右边第一个小于等于他的数在哪 记为right
//然后在这个数和right-1之间内找一个最大值在pos,相同取最左
//则len=pos-i即为所求

int stick[MAXN] = { 0 };
//棍子长度

void getLen(int n) {
	int max = -1;
	for (int i = 0; i < n; i++) {
		int cur = stick[i];
		//记录当前棍子长度
		int pos;
		int right =n;
		for (int r = i+1; r <n; r++ ) {
			//找右边小于等于它的
			if (stick[r] <= cur) {
				right = r;
				break;
			}
		}
		pos = i;
		for (int j = pos+1; j < right; j++) {
			//找最大
			if (stick[j] > stick[pos]) {
				pos = j;
			}
		}
		int len = pos - i;
		if (len && len > max) {
			//如果len不为零并且大于max
			max = len;
		}
		
	}
	cout << max << endl;
}


int main() {
	int n;
	while(~scanf_s("%d", &n)){
		for (int i = 0; i < n; i++) {
			cin >> stick[i];
		}
		getLen(n);
	}

	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator