首页 > ACM题库 > HDU-杭电 > hdu 2387 Online Shopping-模拟[解题报告]C++
2014
01-05

hdu 2387 Online Shopping-模拟[解题报告]C++

Online Shopping

问题描述 :

The Internet becomes more and more important for our daily life. Aside from information retrieval, many people use the web for comfortable shopping from their home PCs. As the number of online customers grows, so does the number of websites dedicated to comparing online prices. Competitive sites need to quickly visualize the cheapest offers for a certain product. Barter & Haggle Inc. has recently been successful in the field of comparing online prices. However, as more and more comparable services appear, B&H has trouble conserving their market share. This is why the company has decided to improve its technology by comparing prices for different online shops and products simultaneously. The engineers have not been capable of implementing the visualization algorithm, though. This is where you come into play.

Given a table of prices for different products at different online stores, you need to find an optimal reordering of the rows and columns. In order to compare different reorderings, we define the table string to be the string of cells that is obtained from a table by appending all columns. An optimal reordering has the smallest table string with respect to lexicographical comparison (the table string is compared cell-wise).

输入:

The inputs start with a line containing a single integer n. Each of the n following lines contains one test case. Each test case starts with two integers 1 <= a, b <= 5, the number of products and online shops respectively.
The table string consisting of the prices separated by single spaces follows. Each price p is given as an integer amount of cents with 0 <= p <= 109.

输出:

The inputs start with a line containing a single integer n. Each of the n following lines contains one test case. Each test case starts with two integers 1 <= a, b <= 5, the number of products and online shops respectively.
The table string consisting of the prices separated by single spaces follows. Each price p is given as an integer amount of cents with 0 <= p <= 109.

样例输入:

2
3 2 3999 5000 4000 4000 12999 9999
4 3 120 120 110 120 80 75 250 50 200 55 80 80

样例输出:

Scenario #1:
3999 5000 4000 4000 12999 9999

Scenario #2:
50 200 250 80 75 120 80 80 55 120 110 120

#include <stdio.h>
#include <malloc.h>
int p[120][5], now, he[6] = {1, 1, 2, 6, 24, 120};
int n, m, **map, **tmp, **ans;
int** dm(int n, int m) {
    int i;
    int *t = (int *)malloc(sizeof(int) * n * m);
    int **pp = (int **)malloc(sizeof(int *) * n);
    for(i = 0; i < n; ++i) {
        pp[i] = t + i * m;
    }
    return pp;
}
void deld(int ** pp) {
    free(*pp);
    free(pp);
}
void p_f(int x) {
    int i, j, bef = now - 1;
    if(x == 0) return;
    for(i = 0; i < x; ++i) {
        for(j = 0; j < 5; ++j) p[now][j] = p[bef][j];
        p[now][i] = p[bef][x];
        p[now][x] = p[bef][i];
        now++;
        for(j = 1; j < x; ++j) p_f(j);
    }
    return;
}
void cmp() {
    int i, k = 0;
    for(i = 0; i < n * m; ++i) {
        if(*(*ans + i) > *(*tmp + i)) {
            k = 1; break;
        }
        if(*(*ans + i) < *(*tmp + i)) break;
    }
    if(k == 1) {
        for(i = 0; i < n * m; ++i) {
            *(*ans + i) = *(*tmp + i);
        }
    }
}
void bl(int a, int b) {
    int i, j;
    for(i = 0; i < n; ++i) {
        for(j = 0; j < m; ++j) {
            tmp[p[a][i]][p[b][j]] = map[i][j];
        }
    }
    cmp();
}
int main() {
    int i, j, t, tt;
    p[0][0] = 0; p[0][1] = 1; p[0][2] = 2; p[0][3] = 3; p[0][4] = 4;
    now = 1;
    for(i = 1; i < 5; ++i) p_f(i);
    /*
    printf("%d\n\n", now);
    for(i = 0; i < 120; ++i) {
        for(j = 0; j < 5; ++j) printf("%d ", p[i][j]);
        printf("\n");
    }
    */
    scanf("%d", &t);
    for(tt = 0; tt < t; ++tt) {
        scanf("%d %d", &n, &m);
        map = dm(n, m);
        tmp = dm(n, m);
        ans = dm(n, m);
        for(i = 0; i < n; ++i) {
            for(j = 0; j < m; ++j) {
                scanf("%d", &map[i][j]);
                ans[i][j] = map[i][j];
            }
        }
        for(i = 0; i < he[n]; ++i) {
            for(j = 0; j < he[m]; ++j) {
                bl(i, j);
            }
        }
        printf("Scenario #%d:\n", tt + 1);
        for(i = 0; i < n * m; ++i) {
            printf("%d", *(*ans + i));
            if(i != (n * m - 1)) printf(" ");
        }
        printf("\n\n");
        deld(ans);
        deld(map);
        deld(tmp);
    }
    return 0;
}

 


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;