头像

HakunaMatatata




离线:7天前


活动打卡代码 AcWing 125. 耍杂技的牛

#include <algorithm>
#include <iostream>
#include <map>
#include <climits>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3F3F3F3F;
#define debug puts("pigtoria bling bling ⚡️⚡️");
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

int main() {
  // https://www.acwing.com/solution/content/845/
  int n;
  cin >> n;
  vector<pii> cow(n);
  int s, w;
  FOR(i, 0, n) {
    cin >> s >> w;
    cow[i].first = s + w;
    cow[i].second = w;
  }
  sort(cow.begin(), cow.end());
  int ans = INT_MIN, sum = 0;
  FOR(i, 0, n) {
    sum -= cow[i].second;
    ans = max(ans, sum);
    sum += cow[i].first;
  }
  cout << ans << endl;
  return 0;
}


活动打卡代码 AcWing 148. 合并果子

// 哈夫曼树 每次合并最小2个树,从N->N-1堆之后,具有最优子结构
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3F3F3F3F;
#define debug puts("pigtoria bling bling ⚡️⚡️");
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

int main() {
  int n, v;
  cin >> n;
  priority_queue<int, vector<int>, greater<int>> minHeap;
  while (n--) {
    cin >> v;
    minHeap.push(v);
  }

  int ans = 0;
  while (minHeap.size() >= 2) {
    int min1 = minHeap.top();minHeap.pop();
    int min2 = minHeap.top();minHeap.pop();
    int val = min1 + min2;
    minHeap.push(val);
    ans += val;
  }
  cout << ans << endl;
  return 0;
}


活动打卡代码 AcWing 104. 货仓选址

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
const int INF = 0x3F3F3F3F;
#define debug puts("pigtoria bling bling ⚡️⚡️");
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

//  证明参见https://www.acwing.com/solution/content/8130/
int main() {
  int n;
  cin >> n;
  vector<int> arr(n + 1);
  FOR(i,1,n+1) cin >> arr[i];
  sort(arr.begin()+1,arr.end());
  int ans = 0;
  FOR(i,1,n+1) ans += abs(arr[i]-arr[(n+1)/2]);
  cout << ans << endl;
  return 0;
}


活动打卡代码 AcWing 913. 排队打水

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
const int INF = 0x3F3F3F3F;

#define debug puts("pigtoria bling bling ⚡️⚡️");
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

int main() {
  int n;
  cin >> n;
  vector<int> arr(n);
  int val;
  FOR(i, 0, n) cin >> arr[i];
  sort(arr.begin(), arr.end());
  partial_sum(arr.begin(), arr.end(), arr.begin());
  long ans = 0;
  for (int i = 0; i < n - 1; i++) {
    ans += arr[i];
  }
  cout << ans << endl;
}


活动打卡代码 AcWing 906. 区间分组

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define pii pair<int, int>
using namespace std;
// 题解参考  https://www.acwing.com/solution/content/14773/
// 当时想错的原因是 没读懂题意, 两两不相交的 区间组 的 个数 两两不相交和 组
class Solution {
 public:
  int rangeGroup(vector<pii> w) {
    sort(w.begin(), w.end(),[](pii p, pii q) -> bool { return p.first < q.first; });
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < w.capacity(); i++) {
      pii p = w[i];
      if (heap.empty() || heap.top() >= p.first) {
        heap.push(p.second);
      } else {
        heap.pop();
        heap.push(p.second);
      }
    }
    return heap.size();
  }
};
int N;
int main() {
  cin >> N;
  vector<pii> w;
  while (N--) {
    int l, r;
    cin >> l >> r;
    w.push_back({l, r});
  }
  Solution INSTANCE;
  int ans = INSTANCE.rangeGroup(w);
  cout << ans;
  return 0;
}




#include <algorithm>
#include <iostream>
#include <vector>

#define pii pair<int, int>
using namespace std;

int INF = 0x3F3F3F3F;

class Solution {
public:
    int range(vector<pii > data) {
        sort(data.begin(), data.end(), [](pii p, pii q) -> bool { return p.second < q.second; });
        int ans = 0;
        int end = -INF;
        const int len = data.size();
        for (int i = 0; i < len; i++) {
            if (end < data[i].first) {// 小于当前左端点,则更新end位当前区间的右端点
                ans++;
                end = data[i].second;
            }
        }
        return ans;
    }
};

int N;
int l, r;

int main() {
    cin >> N;
    vector<pii > data;
    while (N--) {
        cin >> l >> r;
        data.push_back({l, r});
    }
    Solution INSTANCE;
    int ans = INSTANCE.range(data);
    cout << ans;
    return 0;
}


活动打卡代码 AcWing 905. 区间选点

// 按右端点从小到大排序,如果本次end(取右端点)不能包含本次区间,则更新成取本区间的右端点

#include <iostream>
#include <vector>
#include <algorithm>

#define pii pair<int,int>
using namespace std;

bool operator<(pii p1, pii p2) {
    return p1.second < p2.second;
}

int INF = 0x3F3F3F3F;

class Solution {
public:
    int range(vector<pii > data) {
        sort(data.begin(), data.end(), [](pii p, pii q) -> bool { return p.second < q.second; });
        int ans = 0;
        int end = -INF;
        const int len = data.size();
        for (int i = 0; i < len; i++) {
            if (end < data[i].first) {
                ans++;
                end = data[i].second;
            }
        }
        return ans;
    }
};


int N;
int l, r;

int main() {
    cin >> N;
    vector<pii > data;
    while (N--) {
        cin >> l >> r;
        data.push_back({l, r});
    }
    Solution INSTANCE;
    int ans = INSTANCE.range(data);
    cout << ans;
    return 0;
}




#include <iostream>

using namespace std;

class Solution {
public:
    int NumberOf1(int n) {
        int count = 0;
        unsigned int un = n;
        while (un) {
            count += un & 1;
            un = un >> 1; // 高位补0;
        }
        return count;
    }

    int NumberOfOne(int n) {
        int cnt = 0;
        for (int i = 0; i < 32; i++) cnt += (n >> i) & 1;
        return cnt;
    }
};

int main() {
    Solution Instance;
    cout << Instance.NumberOf1(-2) << endl;
    cout << Instance.NumberOfOne(-2) << endl;
    return 0;
}



活动打卡代码 AcWing 809. 最小公倍数

// 最小公倍数*最大公约数 = 两数之积


#include <vector>
#include <iostream>

using namespace std;


int gcd(int a, int b) {
    if (a % b == 0)return b;
    else return gcd(b, a % b);
}

int lcm(int a, int b) {
    return (a * b / gcd(a, b));
}
// 最小公倍数*最大公约数 = 两数之积
int main() {
    int a, b;
    cin >> a >> b;
    cout << lcm(27,15) << endl;
}



解题思路 最小公倍数*最大公约数 = 两数之积


#include <vector>
#include <iostream>

using namespace std;


int gcd(int a, int b) {
    if (a % b == 0)return b;
    else return gcd(b, a % b);
}

int lcm(int a, int b) {
    return (a * b / gcd(a, b));
}
// 最小公倍数*最大公约数 = 两数之积
int main() {
    int a, b;
    cin >> a >> b;
    cout << lcm(a,b) << endl;
}