題目鏈接

題目描述：

隔壁學校地形圖可以通過一個高度矩陣表示，矩陣中每一個位置都有一個數(shù)hi , j表示這個坐標的海拔，我們姑且將其稱為海拔圖，容易發(fā)現(xiàn)，我們可以通過這個矩陣輕松算出隔壁學校的主視圖，左視圖。
相反的，我們卻不能通過主視圖和左視圖唯一確定海拔圖，現(xiàn)在問題來了，已知主視圖左視圖，我們需要知道鏟平隔壁學校的代價上限和下限(即可能的體積最大值與最小值)

輸入
第一行兩個數(shù) n , m (1 <=n ,m<=1000, 0<= hi ,j <= 1000), 分別表示海拔圖的長和寬。
第二行 n 個數(shù)，描述了主視圖每一個位置的高度。
第三行 m 個數(shù)，描述了左視圖每一個位置的高度
輸出
一行兩個數(shù)，分別表示代價最小值與最大值。

樣例輸入：

2 2
1 1
1 1

樣例輸出：

2 4

思路：

• 最大值：構建矩陣，矩陣的每個點是主視圖和左視圖相對應的最小值。這樣滿足構建的圖形符合三視圖，而且矩陣的每個點都有值。
• 最小值：構建的圖形首先滿足主視圖（左視圖），因為相等的點可以共用一個，所以再從左視圖（主視圖）找沒有出現(xiàn)過的點。

ac代碼：

#include<iostream> #include<string.h> #define N 10005 using namespace std; int a[N], b[N]; int vis[N]; int main (){int n, m;//freopen("in.txt", "r", stdin);while(scanf("%d%d", &n, &m) != EOF) {memset(vis, 0, sizeof(vis));int minsum = 0, maxsum = 0;for(int i = 0; i < n; i++) { //先將主視圖相加 cin >> a[i];vis[a[i]]++;minsum += a[i];}for(int j = 0; j < m; j++) { //加上主視圖沒有出現(xiàn)的高度 cin >> b[j];if(vis[b[j]])vis[b[j]]--;elseminsum += b[j];}for(int i = 0; i < n; i++) { //選取矩陣每個點相對應的最小值 for(int j = 0; j < m; j++) {maxsum += min(a[i], b[j]);}}printf("%d %d\n", minsum, maxsum);} return 0; }

總結

以上是生活随笔為你收集整理的2263: neighbor（贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。