将雷达选点问题转化为小岛的区间覆盖为题。

贪心策略：将所有区间按照右端点排序，之后将左端点与当前右端点r0进行比较，若比r0要大，则将r0更新为新的区间的右端点，同时ans++。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
map<PII,int> mp;
struct node{
    double l,r;

    bool operator<(const node& p){  //将区间按照右端点从小到大排序
        return r<p.r;
    }
}a[3000];
double getd(int c,int b)    //得到每个小岛覆盖区间
{
    double a=c*c-b*b;
    return sqrt(a);
}
int idx,n,d,ans;
bool flag;
int main()
{
    cin>>n>>d;
    int x,y;
    for (int i = 1; i <= n; i ++ )
    {
        cin>>x>>y;
        if(y>d) flag=true;  //如果该岛太远，则说明不能覆盖所有岛屿
        if(!mp[{x,y}])
        {
            mp[{x,y}]=i;
            double L=getd(d,y);
            a[idx++]={x-L,x+L}; //将每个小岛的覆盖区间加入数组
        }
    }
    if(flag)
    {
        puts("-1");
        return 0;
    }

    sort(a,a+idx);
    double r0=a[0].r;   //当前右端点
    ans=1;
    for (int i = 1; i < idx; i ++ )
    {
       if(a[i].l>r0)    //当前区间左端点比r0要大，要对右端点进行更新，同时雷达数+1
       {
           r0=a[i].r;
           ans++;
       }
        // cout<<a[i].l<<" "<<a[i].r<<endl;
    }
    cout<<ans;
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int N = 1e5+10;
using namespace std;

int n,a[N];
LL ans,s[N];
int main()
{
    cin>>n;
    for (int i = 1; i <= n; i ++ )
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    for (int i = 1; i <= n; i ++ )
        ans+=a[i]*(s[n]-s[i]);
    cout<<ans<<endl;
    return 0;
}

并查集路径压缩，让每一个信息都加在一个连通块的根节点上，最后让每个点加上其到根节点的信息量。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
int fa[N],d[N],n,m;

int find(int x)  // 并查集
{
    if (fa[x] == x || fa[fa[x]]==fa[x]) return fa[x];
    int root=find(fa[x]);
    d[x]+=d[fa[x]]; //路径压缩
    fa[x]=root;
    return fa[x];
}

int main()
{
    ios::sync_with_stdio(false);
    for(int i=0;i<N;i++) fa[i]=i;
    cin>>n>>m;
    int op,a,b;
    while (m -- )
    {
        cin>>op>>a>>b;
        if(op==1)
        {
            int faa=find(a),fbb=find(b);
            if(faa!=fbb)    
            {
                d[faa]-=d[fbb]; //合并两连通块，让一个连通块根节点的值减去另一个根节点的值
                fa[faa]=fbb;    //之后将父结点进行设置
            }
        }
        else
        {
            int faa=find(a);    //信息加在连通块的根节点上
            d[faa]+=b;
        }
    }

    for (int i = 1; i <= n; i ++ )
    {
        int f=find(i);
        if(f==i) cout<<d[i]<<" "; //为一个连通块根节点，直接输出自己的值
        else cout<<d[i]+d[f]<<" ";  //为某连通块子节点，输出自己的值+联通块的信息量
    }


    return 0;
}

分析

bfs将所有值存入数组q，q从小到大排序，找到最小差值。

C++ 代码

class Solution {
public:
    int q[100],idx;
    int minDiffInBST(TreeNode* root) {
        queue<TreeNode*> Q;
        Q.push(root);
        while(Q.size()) //bfs
        {
            auto t=Q.front(); Q.pop();
            if(t->left) Q.push(t->left);
            if(t->right) Q.push(t->right);
            q[idx++]=t->val;
        }

        sort(q,q+idx);
        int ans=INT_MAX;
        for(int i=0;i<idx-1;i++)
        {
            q[i]=q[i+1]-q[i];
            ans=min(ans,q[i]);     //求最小差值       
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int q[100],idx;
    int minDiffInBST(TreeNode* root) {
        queue<TreeNode*> Q;
        Q.push(root);
        while(Q.size())
        {
            auto t=Q.front(); Q.pop();
            if(t->left) Q.push(t->left);
            if(t->right) Q.push(t->right);
            q[idx++]=t->val;
        }
        sort(q,q+idx);
        int ans=INT_MAX;
        for(int i=0;i<idx-1;i++)
        {
            q[i]=q[i+1]-q[i];
            ans=min(ans,q[i]);            
        }
        return ans;
    }
};

dfs

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int treeDepth(TreeNode* root) {
        if(!root) return 0;
        return max(treeDepth(root->left),treeDepth(root->right))+1;
    }
};

维护一个单调栈，如果当前元素比ans末尾元素小，就让ans末尾弹出，直到ans末尾元素小于当前元素。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

string s,ans="0";
int k;
int main()
{
    cin>>s>>k;
    for(auto c:s)
    {
        while(k && ans.back()>c)
        {
            k--;
            ans.pop_back();
        }
        ans+=c;
    }
    while(k--) ans.pop_back();
    reverse(ans.begin(),ans.end());
    while(ans.size()>1 && ans.back()=='0') ans.pop_back();
    reverse(ans.begin(),ans.end());
    cout<<ans;
    return 0;
}

分析

设置一个比较函数，让较大的排列排在前面。
最后如果一个序列全为0，只用返回一个0。

C++ 代码

class Solution {
public:
    bool static cmp(string a,string b)  //排序函数，从大到小排
    {
        return a+b>b+a;
    }
    string ans;
    string largestNumber(vector<int>& nums) {
        vector<string> v;
        for(auto x:nums)
            v.push_back(to_string(x));

        sort(v.begin(),v.end(),cmp);
        for(auto x:v)
            ans+=x;
        reverse(ans.begin(),ans.end());
        while(ans.size()>1 && ans.back()=='0') ans.pop_back();  //去掉所有前导0
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int M=1e5+10,N=5*M;
struct node{
    int l,r;
    LL sum,d;
}tr[4*N];
int n,m;
LL a[N];
LL gcd(LL a,LL b)
{
    return b?gcd(b,a%b):a;
}
void pushup(node& u,node& l,node& r)
{
    u.sum=l.sum+r.sum;
    u.d=gcd(l.d,r.d);
}
void pushup(int u)
{
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
    if(l==r)
    {
        LL b=a[r]-a[l-1];
        tr[u]={l,r,b,b};
    }
    else{
        tr[u].l=l,tr[u].r=r;
        int mid=(l+r)>>1;
        build(u<<1,l,mid),build(u<<1 | 1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int x,LL v)
{
    if(tr[u].l==x && tr[u].r==x)
    {
        LL b=tr[u].sum+v;
        tr[u]={x,x,b,b};
    }
    else
    {
        int mid=(tr[u].l+tr[u].r)>>1;
        if(x<=mid) modify(u<<1,x,v);
        else modify(u<<1 | 1,x,v);
        pushup(u);
    }
}
node query(int u,int l,int r)
{
    if(tr[u].l>=l && tr[u].r<=r) return tr[u];
    else
    {
        int mid=(tr[u].l+tr[u].r)>>1;
        if(r<=mid) return query(u<<1,l,r);
        else if(l>mid) return query(u<<1|1,l,r);
        else{
            auto left=query(u<<1,l,r);
            auto right=query(u<<1|1,l,r);
            node res;
            pushup(res,left,right);
            return res;
        }
    }

}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);    
    build(1,1,n);
    char op[2];
    int L,R;
    LL D;
    while(m--)
    {
        scanf("%s",op);
        if(*op=='Q')
        {
           scanf("%d%d",&L,&R);
           auto left=query(1,1,L),right=query(1,L+1,R);
           printf("%lld\n",abs(gcd(left.sum,right.d)));
        }
        else{
           scanf("%d%d%lld",&L,&R,&D);
           modify(1,L,D);
           if(R+1<=n) modify(1,R+1,-D); 
        }
    }
    return 0;
}

class Solution {
public:
    bool isUgly(int n) {
        if(!n) return false;
        while(n%2==0) n/=2;
        while(n%3==0) n/=3;
        while(n%5==0) n/=5;
        if(n==1) return true;
        return false;
    }
};