K

题意：求数组中最小值的最靠前编号

思路：模拟即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;cin>>n;
    vector<int> a(n+1);
    int id=1;//记录最小值下标
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        if(a[i]<a[id]) id=i;//只有在小于时更新
    }
    cout<<id<<endl;
    return 0;   
}

F

题意：给定n种前进方式 每一个前进方式都有三个值：ai，bi和ci

ai代表单次可以前进的距离

bi代表每第kbi次（k取1，2，3...）会往后退ci

求到达x时的最小后退次数

思路：我们可以把每个方式的前（bi-1）次白嫖，记录下sum

如果sum已经抵达x，则输出0 。否则，观察对于每一个前进方式，是否存在最优的方式———令ai*bi-ci最大 。

若最大值小于0，则说明无法抵达，否则，一直使用最优方式。

#include<bits/stdc++.h>
using namespace std;
#define int long long 

signed main()
{
    int t;cin>>t;
    while(t--)    
    {
        int n,x;cin>>n>>x;
        int sum=0;
        vector<vector<int>> a(n+1,vector<int>(3,0));
        for(int i=1;i<=n;i++) 
        {
            cin>>a[i][0]>>a[i][1]>>a[i][2];
            sum+=(a[i][0]*(a[i][1]-1));   
        }
        if(sum>=x) 
        {
            cout<<0<<endl;continue;
        }
        int mx=-1e18;
        for(int i=1;i<=n;i++)
        {
            int res=a[i][0]*a[i][1]-a[i][2];
            mx=max(res,mx);
        }
        if(mx<=0) 
        {
            cout<<-1<<endl;continue;
        }
        int cnt=(x-sum)/mx+((x-sum)%mx?1:0);
        cout<<cnt<<endl;
    }
    
}

J

题意：给定一棵树，树的每条边存在一个权值，权值取决于这个边（u，v）中编号uv下标对应的排列的值。

你需要给出一个排列，使得树的权值之和最大。

长度为n的排列是指1-n的数字构成的数组，没有数字缺少且没有数字重复。例如长度为5的排列可以是1，3，5，2，4。

思路：（偷懒使用一下原题的官方题解）

连一条边的准则为：对于一条边的两个点 我们应该存一条由权值大的点指向权值小的点的边

对于上面这个样例 我们应该给予一条链的起点尽量大的权值，给予一条链的末端尽量小的权值（样例1的数据）

（标号为节点编号，标号外的数字为给予的权值，也就是排列中的值）

#include<bits/stdc++.h>
using namespace std;
#define int long long 

signed main()
{
    int t;cin>>t;
    while(t--)    
    {
        int n;cin>>n;
        vector<vector<int>> g(n+1);
        for(int i=1;i<=n-1;i++)
        {
            int u,v,x,y;cin>>u>>v>>x>>y;
            if(x>y) g[u].push_back(v);
            else g[v].push_back(u);
        }
        vector<vector<int>> a(n+1,vector<int>(2,-1));
        function<int(int)> dfs=[&](int u)
        {
            int cnt=0;
            for(auto &v:g[u])
            {
                if(a[v][0]!=-1) cnt+=a[v][0]+1;
                else cnt+=dfs(v)+1;
            }
            a[u][0]=cnt;
            return cnt;
        };
        for(int i=1;i<=n;i++)
        {
            a[i][1]=i;
            if(a[i][0]==-1)
            {
                if(!g[i].size()) a[i][0]=0;
                else dfs(i);
            }
        }
        sort(a.begin()+1,a.end());
        vector<int> ans(n+1);
        int mex=1;
        for(int i=1;i<=n;i++) ans[a[i][1]]=mex++;
        for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
    }
    
}