UVA - 1611 (구조 류)

제목 의 대 의 는 n 길이 의 문자열 을 주어진 것 입 니 다. 길이 가 짝수 인 구간 의 반 대 반 만 교환 (반전 이 아 닌) 하고 9 ^ 6 (최 악의 nlogn 알고리즘) 을 초과 하지 않 고 순 서 를 매 기 는 것 입 니 다.
방법
처음에는 생각 지도 못 하 게 머리 가 사점 에 빠 졌 다.
사실 평소 전달 식 사상 으로 1 을 1 곳 에 두 면 나머지 는 키 문제 다.
1 을 어떻게 빨리 1 곳 에 두 는 지 는 사실 1 곳 은 고려 할 필요 가 없다.만약 에 1. 중심 위치 (짝수 상황 에서 오른쪽 에 있 는 중간 위 치 를 선택) 는 그 다음 에 교환 하면 된다.
나머지 는 양쪽 이 고 순서대로 교환 하면 1 을 중간 에 놓 을 수 있다.그래서 최 악 은 두 번 이 필요 해.그럼 총 시간 복잡 도 최 악 은 2 * n.
다음 코드:

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 10100;
int a[maxn],Id[maxn],n;
struct node{
  int x, y;
  node(int x=0,int y=0):x(x),y(y){}
};
vector ans;
int Swap(int x1,int y1,int x2,int y2){
  ans.push_back(node(x1,y2));
  for(int i=x1,j=x2;i<=y1;i++,j++){
     swap(Id[a[i]],Id[a[j]]);
     swap(a[i],a[j]);
  }
}
int main()
{
    int T=0;
    scanf("%d",&T);
    while(T--){
      scanf("%d",&n);
      for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        Id[a[i]]=i;
      }
      ans.clear();
      for(int i=1;i<=n;i++){
        if(Id[i]==i) continue;
         int m=(i+n+1)/2;
         int id=Id[i];
         if(id!=m){
            if(id

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

asp.net+sqlserver 가 실현 하 는 간단 하고 효율 적 인 권한 설계 예시

대부분의 시스템 은 권한 시스템 이 있다.일반적으로,그것 은 어떤 페이지 에 대한 접근 을 통제 할 수 있다.일부 필드,컨트롤 이 보이 거나 보이 지 않 습 니 다.gridview 의 데 이 터 를 삭제 할 수 있 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

UVA - 1611 (구조 류)

좋은 웹페이지 즐겨찾기