IceBorworntat's Blog

competitive coder

Island

Friday, January 1, 2021, 08:00 PM
Programming
Cplusplus
Contest

ถมดินรวมเกาะ(island)

โจทย์

อธิบายโจทย์
เรามีพื้นที่ทั้งหมด N พื้นที่ และต้องการรวมเกาะให้เหลือ K เกาะ

เฉลย
ให้เรารับค่า island[i] ถ้า island[i] มีค่าน้อยกว่า 0 ให้บวกค่าใน sum ถ้า island[i] มากกว่า 0 ให้ นำค่า sum มาใส่ที่ dp[island_cnt]
Source Code(C++) :

#include<iostream>
#include<vector>
using namespace std;

int main (void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,k,sum=0,island_cnt=0;
  cin >> n >> k;
  vector<int>island(n),dp;
  for(int i=0;i<n;++i){
    cin >> island[i];
    if(island[i] < 0){
      sum += abs(island[i]) + 1;
    }
    else{
      dp.push_back(sum);
      sum = 0;
      island_cnt++;     //ใช้นับจำนวนเกาะที่มี
    }
  }
  return 0;
}

แต่ว่าถ้าทำตามโต้ดด้านบนจะเกิดบัคขึ้น เพราะจะนับจำนวนเกาะผิดพลาดเพราะถ้า island[i] > 0 และอยู่ติดกับพื้นดินจะ ไม่นับเป็นเกาะ เราจึงเพิ่ม mark เข้าไป
Source Code(C++) :

#include<iostream>
#include<vector>
using namespace std;

int main (void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,k,sum=0,island_cnt=0;
  cin >> n >> k;
  bool mark = false;
  vector<int>island(n),dp;
  for(int i=0;i<n;++i){
    cin >> island[i];
    if(island[i] < 0){
      sum += abs(island[i]) + 1;
      mark = true;
    }
    if(island[i] < 0 and mark == true){
      dp.push_back(sum);
      sum = 0;
      island_cnt++;
      mark = false;
    }
  }
  return 0;
}

ต่อมาในส่วนของการหาจุดที่ควรถมสามารถใช้ Greedy Algorithm ได้โดยการเรียงเลขในอาร์เรย์ dp
Source Code(C++) :

#include<iostream>
#include<vector>
using namespace std;

int main (void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,k,sum=0,island_cnt=0;
  cin >> n >> k;
  bool mark = false;
  vector<int>island(n),dp;
  for(int i=0;i<n;++i){
    cin >> island[i];
    if(island[i] < 0){
      sum += abs(island[i]) + 1;
      mark = true;
    }
    if(island[i] < 0 and mark == true){
      dp.push_back(sum);
      sum = 0;
      island_cnt++;
      mark = false;
    }
  }
  dp.push_back(sum);
  sort(dp.begin(),dp.end());
  return 0;
}

จากนั้นเราจะบวกที่ที่ต้องถมจนกว่าจะเหลือเกาะเท่ากับ k เกาะ
Source Code(C++) :

#include<iostream>
#include<vector>
using namespace std;

int main (void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,k,sum=0,island_cnt=0;
  cin >> n >> k;
  bool mark = false;
  vector<int>island(n),dp;
  for(int i=0;i<n;++i){
    cin >> island[i];
    if(island[i] < 0){
      sum += abs(island[i]) + 1;
      mark = true;
    }
    if(island[i] < 0 and mark == true){
      dp.push_back(sum);
      sum = 0;
      island_cnt++;
      mark = false;
    }
  }
  dp.push_back(sum);
  sort(dp.begin(),dp.end());
  int ans = 0;
  for(int i=0;i<island_cnt-k;++i){
    ans += dp[i];
  }
  cout << ans << endl;
  return 0;
}

IceBorworntat

author