희소 행렬 쾌속 변환 알고리즘 구현

2224 단어
전환 에 있어 서 만약 에 우리 가 전 환 된 요소 의 순 서 를 고려 하지 않 는 다 면 실제 적 으로 3 원 그룹 전 체 를 한 번 훑 어보 고 x 와 y 의 값 을 교환 하면 ok 입 니 다.빠 른 전환 알고리즘 이 필요 한 이 유 는 3 원 그룹 이 초기 에 각 3 원 그룹 x 의 값 에 따라 큰 것 에서 작은 것 으로 바 뀌 었 다 면 우 리 는 전 치 된 후에 도 그 순 서 는 x 의 값 크기 에 따라 배열 되 기 를 바 랍 니 다.
알고리즘 사상
이 문제 에 대해 우 리 는 먼저 y 의 모든 수치 수량 을 통계 할 수 있다. 그 다음 에 우 리 는 모든 y 가 x 로 전 치 된 후에 모든 x 가 몇 개 있 는 지 계산 할 수 있다. 즉, 우 리 는 우리 가 전 치 된 3 원 조 의 시작 위 치 를 알 수 있다.예 를 들 어 우리 가 다음 과 같은 3 원 조 가 있다 고 가정 한다.
//Origin matrix
   x  | y  | value
  ----------------
   1    4     0
   1    2     1
   1    1     -3
   2    3     4
   3    4     9
   3    3     1
   4    1     2

그러면 우 리 는 Y 를 한 번 훑 어 볼 수 있 습 니 다. 1, 2, 3, 4 의 수 는 각각 2, 1, 2, 2 입 니 다.그러면 우리 가 전 치 된 3 원 조 의 배열 은 반드시 이렇다.
             
x=1    x=2        x=3  x=4
|_ _   | _        |_ _ |_ _

만약 그렇다면 우 리 는 원 행렬 의 모든 3 원 그룹 에 대해 Y 의 수치 에 따라 우리 가 넣 을 위 치 를 찾 을 수 있다 는 것 을 알 수 있다. 즉, x 의 수치 시작 을 가리 키 는 지침 (xStart 배열 기록) 이다.그리고 어떤 포인터 가 가리 키 는 구역 에 한 개의 수 를 넣 을 때마다 포인터 가 한 자 리 를 뒤로 이동 하도록 합 니 다.이렇게 해서 우 리 는 원래 의 행렬 을 한 번 훑 어보 기만 하면 전 치 된 행렬 을 얻 을 수 있다.
코드 구현
내 가 이전에 언급 한 x 를 가리 키 는 서로 다른 값 의 지침 을 어떻게 얻 는 지 에 대해 우 리 는 두 개의 보조 배열 yCount & xStart 가 필요 하 다. 먼저 yCount 를 얻 은 다음 에 yCount 에 따라 xStart 즉 우리 가 원 하 는 지침 을 계산 해 야 한다.
//Origin matrix
/* x  | y  | value
  ----------------
   1    4     0
   1    2     1
   1    1     -3
   2    3     4
   3    4     9
   3    3     1
   4    1     2
*/
#include
using namespace std;
int yCount[100],xStart[100];        //two extra array
class Node{
public:
    Node(){}
    int x;
    int y;
    int value;
};
Node originMat[100];
Node transMat[100];
void getyCount(int n){
    for(int i=0;i>n;
    cout<>originMat[i].x>>originMat[i].y>>originMat[i].value;
    }
    fastTransMat(n);
    display(n);
}

원본 글 은 제 블 로그 loveSnowBest 's blog 에 올 라 왔 습 니 다.
MBCS 로그 인쇄(1)
[BZOJ 4326] [NOIP 2015] 운송 계획 (2 점 + dfs 순서 + 트 리 차이 점)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage