牛客练习赛69（A，B，C）

时间复杂度

题意：给出一个t，表示分钟数，要你计算出t分钟后时钟上面时针和分针的更小的那个夹角的大小。
思路：一个简单模拟，看似简单，实际上要注意的是四舍五入，我们习惯上分别计算时针和分针走的角度，然后进行一个做差，问题就很可能出在做差的时候，做差下来小于180度没话说，但是一旦超过一百八十度的时候我们肯定想到的是做差，然而做差下来之后进行四舍五入的话很可能把改进位的改为舍去了，两者相差了1，所以要进行一个分情况来讨论。注意用double类型的变量即可。
代码：

#include<bits/stdc++.h> 
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n--){
        double t;
        cin>>t;
        double m=t*6,h=t/2.0;
        while(m>360)  m-=360;
        while(h>360)  h-=360;
        double temp1=abs(m-h),temp2=360-temp1;
        temp1=min(temp1,temp2);
        double tmp=(int)temp1;
        if(temp1!=tmp)  temp1+=0.5;
        cout<<temp1<<endl;
    }
    return 0;
}

划分

题意：这个题目还是比较有意思的，我们会发现，val(i,j)其实就是原数组里面的前i*j大的数之和，所以我们很容易的想到先用前缀和进行一个处理，然后直接累加到答案里面即可。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100010];
ll sum[100010];
bool cmp(int a,int b){
    return a>b;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
    int x,y;
    cin>>x>>y;
    ll ans=0;
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            int temp=i*j;
            ans+=sum[temp];
        //    cout<<ans<<endl;
        }
    }
    cout<<ans<<endl;
    return 0;
}

旅行

题意：题目的意思很好理解，就是给出一个图，然后在图中找出一个n的排列，使得这个排列的相邻点之间的距离之和最大，其实很容易看出这个和我们求最小生成树是一样的做法，只是这个是要使最后的结果值最大，所以，这应该就是要我们求一个最大的生成树，我们可以利用并查集进行一个处理，我们先进行一个对边权从大到小的排序，然后抽出每条边，合并这条边长的两端的点，如果不在同一个集合里面的话，那么就累加到答案里面。
代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
using namespace std;
typedef long long ll;
const int N=5e5+1000; 
struct node{
    ll x,y,w;
}Node[N];
ll fa[N],n,m;
bool cmp(node a,node b){
    return a.w>b.w;
}
ll find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)  fa[i]=i;
    for(int i=1;i<=m;i++){
        cin>>Node[i].x>>Node[i].y>>Node[i].w;
    }
    sort(Node+1,Node+1+m,cmp);
    ll ans=0;
    for(int i=1;i<=m;i++){
        int fx=find(Node[i].x),fy=find(Node[i].y);
        if(fx==fy) continue;
        ans+=Node[i].w;
        fa[fx]=fy;
    }
    cout<<ans<<endl;
    return 0;
}