并查集

我怎么感觉碰到题目想不到究竟怎么实际用呢

实现找图有无环

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define VERTICES 6
using namespace std;
void init(int parent[],int rank[]){
    for(int i = 0;i < VERTICES;i++){
        parent[i] = -1;
        rank[i] = 0;
    }
    return;
}

int find_root(int x,int parent[]){
    int x_root = x;
    while(parent[x_root] != -1){
        x_root = parent[x_root];
    }
    return x_root;
}

/*1->union successfully,0->failed*/
int union_vertices(int x,int y,int parent[],int rank[]){
    int x_root = find_root(x,parent);
    int y_root = find_root(y,parent);
    if(x_root == y_root) return 0;
    else {
        if(rank[x_root] > rank[y_root]){
            parent[y_root] = x_root;
        }
        else if(rank[x_root] < rank[y_root]){
            parent[x_root] = y_root;
        }
        else{
            parent[x_root] = y_root;
            rank[y_root] ++ ; 
        }
        return 1;
    }
}

int main()
{
    int parent[VERTICES] = {0};
    int rank[VERTICES] = {0};
    int edges[6][2] = {{0,1},{1,2},{1,3},{2,4},{3,4},{2,5}};
    init(parent,rank);
    int i;
    for(i = 0;i < 6;i++){
        int x = edges[i][0];
        int y = edges[i][1];
        if(union_vertices(x,y,parent,rank) == 0){
            printf("cycles\n");
            return 0;
        }
    }
    printf("no cycles\n");
    return 0;
}


下面是相应的一道贪心+并查集的题目

思路:
关键是要在保质期前卖出
代码在此

#include <iostream>
#include <algorithm>
#include <string.h>
#define MaxSize 10010
using namespace std;

struct goods{
    int val,date;
}; 

goods G[MaxSize];
int parent[MaxSize];

int n;

int find_root(int x){
    if(parent[x] < 0) return x;
    return parent[x] = find_root(parent[x]);
}


bool cmp(goods A,goods B){
    return A.val > B.val;
}

int main()
{
    while(~scanf("%d",&n)){
        memset(parent,-1,sizeof(parent));
        for(int i = 0;i < n;i++){
            cin>>G[i].val>>G[i].date;
        }
        sort(G,G+n,cmp);
        int ans = 0;
        for(int i = 0;i < n;i++){
            int t = find_root(G[i].date);
            if(t > 0){
                ans += G[i].val;
                parent[t] = t - 1;
            }
        }
        cout<<ans<<endl;
    }
}

二分,尺取,倍增


题意:男生女生手中的数字之和大于K的组合尽量多。
思路:排序后数组1从左端看,数组2从右端看

代码在此

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

void solve(){
    int num,k;
    cin>>num>>k;
    int a[num],b[num];
    for(int i = 0;i < num;i++){
        cin>>a[i];
    }    
    for(int i = 0;i < num;i++){
        cin>>b[i];
    }
    sort(a,a+num);
    sort(b,b+num);
    int p = 0,q = num-1,cnt = 0;
    while(p < num && q >= 0){
        if(a[p] + b[q] >= k){
            cnt ++ ;
            p++;q--;
        }
        else p++;
    }
    cout<<cnt<<endl;
    return ;
}

int main()
{
    int n;cin>>n;
    while(n--){
        solve();
    }
    return 0;
}


题意:两种吃法,A每次吃掉K个,B每次吃掉省的10%,问求出最小的K使得A吃掉的多余一半
思路:由于吃掉的和k正相关,用二分查找

代码在此

#include <iostream>
using namespace std;

bool check(long long k,long long sum){
    long long tmpsum = sum; 
    long long all = 0;
    bool is_v = true;
    while(sum){
        if(is_v && sum >= k){
            is_v = false;
            all += k;
            sum -= k;
        }
        else if(is_v && sum < k){
            all += sum;
            break;
        }
        else{
            long long a = sum / 10;
            sum -= a;
            is_v = true;
        }
    }
    if(all * 2 >= tmpsum) return true;
    else return false;
}

int main()
{
    long long n;
    cin>>n;
    long long p = 1;long long q = n;
    while(p < q){
        long long mid = (p + q) / 2;
        if(check(mid,n)){
            q = mid;
        }
        else p = mid + 1;
    }
    cout<<p<<endl;
    return 0;
}


大意:给一串由a,b组成的字串,可以改变k次字母,问最长的相同的字串的长度
思路:尺取法分别求出a和b的最长字串长度

代码在此

#include <iostream>
using namespace std;
string s;

int solve(int n,int k,char c){
    int l = 0,r = 0,cnt = 0,ans = -1;
    while(l < n && r < n){
        while((s[r] == c || cnt < k) && r < n){
            if(s[r] != c){
                cnt++;
            }
            r++;
        } 
        ans = max(ans,r-l);
        while(l < r && s[l] == c){
            l++;
        }
        l++;
        cnt--;
    }
    return ans;
}

int main()
{
    int n,k;
    cin>>n>>k;
    cin>>s;
    cout<<max(solve(n,k,'a'),solve(n,k,'b'));
    return 0;
}


大意:给一串数字,如果第i个数后面的数字有比它小的,则这个数就是bad_num,问有多少个bad_num
思路:从右往左看,找到右面所有数里最小的数,与现在的比较。

代码在此

#include <iostream>
using namespace std;

void solve()
{
    int t;
    cin>>t;
    int num[t],m = 1000010,ans = 0;
    for(int i = 0;i < t;i++){
        cin>>num[i];
    }
    if(t == 1) {
        cout<<0<<endl;
        return;
    }
    for(int i = t-2;i >= 0;i--){
        m = min(m,num[i+1]);
        if(num[i] > m) ans++;
    }
    cout<<ans<<endl;
    return;
}

int main()
{
    int n;cin>>n;
    while(n--){
        solve(); 
    }    
    return 0;
} 


思路:和上面Candies很像的题目,利用二分法判断~

代码在此

#include <iostream>
#define PI 3.1415926
#define eps 1e-6
using namespace std;
typedef long long ll;
const ll maxn = 2e5 + 5;
double a[maxn];

int n,k;

int check(double x){
    int num = 0;
    for(int i = n-1;i >= 0;i--){
        num += (a[i] / x);
    }
    if(num >= k) return 1;
    else return 0;
}

int main()
{
    int t;
    cin>>t;
    while(t--){
        cin>>n>>k;
        k += 1;
        double l = 0,r = 0,ans = 0;
        for(int i = 0;i < n;i++){
            cin>>a[i];
            a[i] = a[i] * a[i] * PI;
            r = max(r,a[i]);
        }
        while(r - l > eps){
            double mid = (l + r) / 2;
            if(check(mid)){
                ans = mid;
                l = mid;
            }
            else r = mid;
        }
        printf("%.4lf\n",ans);
    }
    return 0;
}


大意:给汉堡的样式,由BSC组成,分别给BSC的已有数量和单价,以及有的钱数,问最多做多少个汉堡包。
思路:数据量太大了,很明显是二分,二分汉堡包的数量,check能不能做mid的汉堡,正向思维。
注意要想到某个材料不需要的情况。

代码在此

#include <iostream>
#include <string.h> 
using namespace std;
typedef long long ll;

ll num_B = 0,num_S = 0,num_C = 0,va,vb,vc,a,b,c,mon;
bool check(ll A){
    ll monb = (A * num_B - a) * va;
    ll mons = (A * num_S - b) * vb;
    ll monc = (A * num_C - c) * vc;
    if(monb < 0) monb = 0;
    if(mons < 0) mons = 0;
    if(monc < 0) monc = 0;
    if(monb + mons + monc <= mon) return true;
    else return false;
}

int main()
{
    string s;
    cin>>s;
    cin>>a>>b>>c>>va>>vb>>vc>>mon;
    ll l = s.length();    
    for(ll i = 0;i < l;i++){
        if(s[i] == 'B') num_B++;
        else if(s[i] == 'S') num_S ++ ;
        else num_C++;
    }
    ll left = 0,right = 1e13,ans;
    while(left < right){
        ll mid = (left + right) / 2;
        if(check(mid)){
            left = mid + 1;
        }
        else{
            right = mid;
        }
    }
    cout<<left-1<<endl;
    return 0;
} 

今天做的都不难欸。

Last modification:June 27th, 2020 at 10:21 pm
请赏我杯奶茶,让我快乐长肉