home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Maximum Number of Ones (จำนวน 1 สูงสุด) ใน C++

สมมติว่าเรามีเมทริกซ์ M ขนาด w x h โดยที่ทุกเซลล์มีค่า 0 หรือ 1 และ sub-matrix สี่เหลี่ยมจัตุรัสขนาด l x l ใดๆ ของ M มีจำนวน 1 สูงสุด maxOnes เราต้องหาจำนวน 1 สูงสุดที่เมทริกซ์ M อาจมีได้

ดังนั้น หากอินพุทคือ w = 3, h = 3, l = 2, maxOnes = 1 ผลลัพธ์จะเป็น 4 เนื่องจากในเมทริกซ์ 3x3 ไม่มี sub-matrix 2x2 ไหนที่มี 1 มากกว่า 1 ตัว วิธีที่ดีที่สุดที่มี 4 ตัว 1 คือ:

101
000
101

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

  • ret := 0

  • สร้างอาเรย์ 2 มิติ sq ขนาด n x n

  • for i := 0 ถึง height-1, for j := 0 ถึง width-1: เพิ่ม sq[i mod n][j mod n] ขึ้น 1

  • กำหนดอาเรย์ v

  • for i := 0 ถึง n-1, for j := 0 ถึง n-1: ใส่ sq[i][j] ลง v

  • จัดเรียง v เรียงจากมากไปน้อย

  • for i := 0, j := 0; i < ขนาดของ v และ j < maxOnes; i++, j++: ret += v[i]

  • คืนค่า ret

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maximumNumberOfOnes(int width, int height, int n, int maxOnes) {
        int ret = 0;
        vector> sq(n, vector(n));
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                sq[i % n][j % n]++;
            }
        }
        vector v;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                v.push_back(sq[i][j]);
            }
        }
        sort(v.rbegin(), v.rend());
        for (int i = 0, j = 0; i < v.size() && j < maxOnes; i++, j++) {
            ret += v[i];
        }
        return ret;
    }
};

int main() {
    Solution ob;
    cout << (ob.maximumNumberOfOnes(3, 3, 2, 1));
    return 0;
}

อินพุต

3, 3, 2, 1

เอาต์พุต

4