BC-Round 3 HDU 4908

1022 단어 수제BC
HDU     4908
제목 링크: 클릭하여 링크 열기
처음에 제목을 봤을 때 제목에 있는 median number의 뜻이 중간의 수인 줄 알았어요.역시 영어는 잘 못해...두 번 냈어요.나중에 경기를 봤을 때 스크롤은 중위수라는 뜻이었어요.다시 할 때는 두 개의 순환으로 옮겨다니다가 결국은 TLE가 되었다.그때는 dp로 하려고 했지만 dp신마는 매번 공식을 찾지 못했다.수학은 진심으로 급하다.다른 사람의 생각을 많이 본 후에 기본적으로 두 가지 방법으로 나뉘는데 하나는 내가 아래에 붙인 것이고 또 하나는 조합수학이다.하지만 수학은...크크.그래서 묵묵히 첫 번째를 이해했어요...
ans의 0, 1은 자열의 길이가 홀수임을 확보하는 데 사용되고 이를 바탕으로 m위치의 전후 두 번의 비교를 통해 길이가 홀수인 자열은 big수와 small수가 꼭 같은 수량으로 하고 m 자체를 자열의 1로 한다.코드는 길지 않지만 생각해 볼 만하다. 자신이 사용하지 않은 방법이다.
#include
#include
#define MAXN 40005

int a[MAXN];
int ans[2][MAXN*2];

int main()
{
	int n,m;
	int cnt;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		int i;
		int x;
		int big,small;
		for(i=0;i=0;--i)
		{
			if(a[i]>a[x])
				big++;
			else
				small++;
			ans[(x-i)&1][big-small+MAXN]++;
		}
		small=big=0;
		for(i=x;ia[x])
				big++;
			else if(a[i]

좋은 웹페이지 즐겨찾기