机试重点题-2019

B：数字配对

考察：map容器的应用

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int n;
map<int, int> mp;

int main()
{
    cin >> n;
    
    for(int i = 0; i<n; i++)
    {
        int temp;
        cin >> temp;
        mp[temp] ++;
    }
    
    map<int, int> :: iterator itor = mp.begin();
    
    while(itor != mp.end())
    {
        if(itor->second % 2 != 0)
        {
            cout << itor->first << endl;
            break;
        }
        itor++;
    }
    return 0;
}
/*
13
2 5 1 3 5 2 5 1 4 1 4 5 1
ouput:3
5
12345 123456789 1234567 123456789 12345
ouput:1234567
*/

D：修路的最小代价

考察：最小生成树

Kruskal算法解决：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010, M = 20010;
int n, m;
int h[N], e[M], ne[M], idx;
int p[N];

struct Edge{
    int a, b, w;
}edges[M];

void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m, cmp);
    int res = 0, cnt = 0;
    
    for(int i = 0; i<m; i++)
    {
        int a = edges[i].a;
        int b = edges[i].b;
        int w = edges[i].w;
        
        a = find(a), b = find(b);
        
        if(a != b)
        {
            p[a] = b;
            cnt ++;
            res += w;
        }
    }
    
    if(cnt == n - 1) return res;
    else return -1;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    
    for(int i = 0; i<n; i++) p[i] = i;
    
    for(int i = 0; i<m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b), add(b, a);
        edges[i] = {a, b, w};
    }
    
    int t = kruskal();
    cout << t << endl;
    
    return 0;
}
/*
5 8
0 1 5
0 2 1
0 3 2
1 2 3
2 3 6
4 1 4
4 2 2
4 3 3
ouput:
8
*/

E：炮台放置

 考察：DFS

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010, M = 1010;
char g[N][M];
int n, m;
int cnt = 0, max_cnt = 0;

void place(int row, int col)
{
    //向上扫描
    for(int i = row - 1; i>0; i--) {
        if(g[i][col] == 'p') return;
        if(g[i][col] == 'x') break;
    }
    //向下扫描
    for(int i = row + 1; i<=n; i++) {
        if(g[i][col] == 'p') return;
        if(g[i][col] == 'x') break;        
    }
    //向左扫描
    for(int j = col - 1; j>0; j--)
    {
        if(g[row][j] == 'p') return;
        if(g[row][j] == 'x') break;
    } 
    //向右扫描
    for(int j = col + 1; j<=m; j++){
        if(g[row][j] == 'p') return;
        if(g[row][j] == 'x') break;
    }
    
    g[row][col] = 'p'; 
    cnt ++; //可放炮台数加1 
    max_cnt = max(max_cnt, cnt);//更新最大炮台数 

    
    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=m; j++)
            if(g[i][j] == '.')
                place(i, j); //只要是个.就尝试放炮
    
    g[row][col] = '.'; //恢复现场，进行下一轮放置
    cnt --; 
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=m; j++)
            cin >> g[i][j];

    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=m; j++)
            if(g[i][j] == '.')
                place(i, j);
    
    cout << max_cnt << endl;
                
    return 0;
}
/*
4 4
.x..
....
x...
....

2 2
.x
x.

5 5
.....
.x..x
..x..
.....
.x...
*/

F：饭卡

HDU2546 原题

考察：贪心 + 背包

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1010, M = 1010;

int n, m, k;//菜数量，余额，输入组数 
int f[N][M]; //f[i][j]：在余额为j的情况下，从前i道菜里购买所能花费的最大方案 
int price[N];

int main()
{
    while(cin >> n && n != 0)
    {
        for(int i = 1; i<=n; i++) cin >> price[i];
        cin >> m;
        if(m < 5)
        {
            cout << m << endl; //钱不够，余额还是m
            continue;
        }
        
        sort(price, price + n + 1);
        //注意题设条件，每购买一件商品之前先判断有没有五块钱 
        int max_price = price[n];
        m -= 5; //先花5元钱买最贵的菜，根据题目条件一定可以买成功 
        //剩余的钱再用01背包解决 
        for(int i = 1; i<=n-1; i++){
            for(int j = 5; j<=m; j++) {
                f[i][j] = f[i - 1][j];
                if(j >= price[i])
                    f[i][j] = max(f[i][j], f[i - 1][j - price[i]] + price[i]);
            }
        }
        //之前m花了5元钱买了最贵的菜要加回来
        //再减去买的最贵的菜价，再减去从前n-1道菜里用"m"(m-5)买菜的价格 
        int remain = m + 5 - price[n] - f[n-1][m];
        cout << remain << endl; 
    }
    
    return 0;
}
/*
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
ouput:
-45
32
*/