#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=510,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];

void dijstra(){
  memset(dist,0x3f,sizeof dist);
  dist[1]=0;

  for(int i=1; i<=n; i++){
    int t=-1;
    for(int j=1; j<=n; j++)
        if(!st[j] && (t==-1 || dist[t]>dist[j]))
          t=j;
    st[t]=true;

    int j;
    for(int j=1; j<=n; j++)
        if(!st[j])
        dist[j]=min(dist[j],dist[t]+g[t][j]);
  }
  if(dist[n]==INF) dist[n]=-1;
}

int main(){
  cin>>n>>m;
  memset(g,0x3f3f,sizeof g);
  int a,b,c;
  for(int i=0; i<m; i++){
    cin>>a>>b>>c;
    g[a][b]=min(g[a][b],c);
  }
  dijstra();
  cout<<dist[n]<<endl;
  return 0;
}

#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int N=40;
int inorder[N],postorder[N];
unordered_map<int,int>l,r,pos;
int n;

int build(int il,int ir,int pl,int pr){
   int root=postorder[pr];
   int k=pos[root];
   if(il<k) l[root]=build(il, k-1, pl, k-1-il+pl);
   if(ir>k) r[root]=build(k+1, ir, k-il+pl, pr-1);
   return root;
}

void bfs(){
  queue<int>q;
  q.push(postorder[n-1]);
  while(!q.empty()){
    int c=q.front();
    q.pop();
    cout<<c<<" ";
    if(l.count(c)) q.push(l[c]);
    if(r.count(c)) q.push(r[c]);
  }
  cout<<endl;
}


int main(){

  cin>>n;
  for(int i=0; i<n; i++)
    cin>>postorder[i];
  for(int i=0; i<n; i++){
    cin>>inorder[i];
    pos[inorder[i]]=i;
  }
  build(0,n-1,0,n-1);
  bfs();
  return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int p[N],cnt[N];
int n,m,q;
int a,b;

int Find(int x){
  if(p[x]!=x) p[x]=Find(p[x]);
  return p[x];
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1; i<=n; i++){
    p[i]=i;
    cnt[i]=1;
  }
  string c;
  while(m--){
    cin>>c;
    if(c=="C"){
        scanf("%d%d",&a,&b);
        if( Find(a)==Find(b))
            continue;
        cnt[Find(b)]+=cnt[Find(a)]; //第28,29两行的顺序不能颠倒
        p[Find(a)]=Find(b);         //否则将出错，总结起来就是“先交兵，再合并”

    }
    else if(c=="Q1"){
        scanf("%d%d",&a,&b);
        if(Find(a)==Find(b)) puts("Yes");
        else puts("No");
    }
    else{
        scanf("%d",&a);
        cout<<cnt[Find(a)]<<endl;
    }
  }
  return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=2e4+5;
int p[N];
int n,m,q;

int Find(int x){
  if(p[x]!=x) p[x]=Find(p[x]);
  return p[x];
}

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1; i<=n; i++) p[i]=i;
  int a,b;

  while(m--){
    scanf("%d%d",&a,&b);
    p[Find(a)]=Find(b);

  }
  cin>>q;
  while(q--){
    scanf("%d%d",&a,&b);
    if(Find(a)==Find(b)) puts("Yes");
        else puts("No");
  }
  return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5;
int p[N];
int n,m;

int Find(int x){
  if(p[x]!=x) p[x]=Find(p[x]);
  return p[x];
}

int main(){
  cin>>n>>m;
  for(int i=1; i<=n; i++) p[i]=i;
  while(m--){
    char c;
    int a,b;
    cin>>c>>a>>b;
    if(c=='M'){
        p[Find(a)]=Find(b);
    }
    else{
        if(Find(a)==Find(b)) puts("Yes");
        else puts("No");
    }
  }
  return 0;
}

题目描述

思路简单是简单，但是就是想不到啊
具体步骤：

1、排序
2、因为序列的所有数都是从“1”开始，白手起家的
   因此，从第i个数开始，判断前i-1个数的和是否大于或等于第i个数
   若是，则没问题；
   否则，则不行。

举一组具体的数据：

a[]={1,x,y,z...}（排序后）
则1>=x;
1+x>=y;
1+x+y>=z;

那么，对于z后面的第一个数符合条件的取值范围为：[z,1+x+y+z]
至于推理证明，欢迎大佬指教！

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;


int main(){
  int t;
  cin>>t;
  while(t--){
    int  n;
    cin>>n;
    int a[n];
    for(int i=0; i<n; i++)
        cin>>a[i];
    sort(a,a+n);

    LL sum=1;
    bool flag=true;
    for(int i=0; i<n; i++){
        if(sum>=a[i]) { if(i) sum+=a[i];}
        else { flag=false; break;}
    }
    if(flag)  puts("YES");
    else puts("NO");
  }
  return 0;
}

#include<iostream>
using namespace std;
const int N=3e5+5;
int n,k;
int q[N],tt=-1,hh;
int a[N],sum[N];

int main(){
  int n,m;
  cin>>n>>m;

  for(int i=1; i<=n; i++){
    scanf("%d",&a[i]);
    sum[i]+=sum[i-1]+a[i];
  }
  int res=sum[1];
  q[++tt]=0;
  for(int i=1; i<=n; i++){
    if(hh<=tt && i-q[hh]>m) hh++;

    if(i>q[hh])
     res=max(sum[i]-sum[q[hh]],res);
//     printf("%d %d %d    %d\n",q[hh],sum[i],sum[q[hh]],res);

    while(hh<=tt && sum[q[tt]]>sum[i]) tt--;
     q[++tt]=i;

  }
  cout<<res<<endl;
  return 0;
}

#include<iostream>
using namespace std;
const int N=1e6+5;
int n,k;
int q[N],tt=-1,hh,a[N];

int main(){
  cin>>n>>k;
  for(int i=0; i<n; i++)
    scanf("%d",&a[i]);

  for(int i=0; i<n; i++){
    if(hh<=tt && i-q[hh]+1>k) hh++;
    while(hh<=tt && a[q[tt]]>a[i]) tt--;
    q[++tt]=i;
    if(i>=k-1) cout<<a[q[hh]]<<" ";
  }
  cout<<endl;

  tt=-1,hh=0;
  for(int i=0; i<n; i++){
    if(hh<=tt && i-q[hh]+1>k) hh++;
    while(hh<=tt && a[q[tt]]<a[i]) tt--;
    q[++tt]=i;
    if(i>=k-1) cout<<a[q[hh]]<<" ";
  }
  cout<<endl;
  return 0;
}

#include<iostream>
using namespace std;
const int N=1e5+5;
int n;
int stk[N],t;

int main(){
  int n;
  cin>>n;
  while(n--){
    int x;
    cin>>x;

    while(t && stk[t]>=x) t--;
    if(t) cout<<stk[t]<<" ";
    else cout<<"-1 ";
    stk[++t]=x;
  }
  cout<<endl;
  return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
const int N=1e5+5,P=131;
char str[N];
ull p[N],h[N];

ull get(int l,int r){
  return (h[r]-h[l-1]*p[r-l+1]);
}

int main(){
 int n,m;
 scanf("%d%d%s",&n,&m,str+1);

 p[0]=1;
 for(int i=1; i<=n; i++){
    p[i]=p[i-1]*P;
    h[i]=h[i-1]*P+str[i];
 }

 int l1,r1,l2,r2;
 for(int i=0; i<m; i++){
    scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
    if(get(l1,r1)==get(l2,r2)) puts("Yes");
    else puts("No");
 }
 return 0;
}