谈论最激烈的莫过于D题了！
看过的两种做法不得不ORZ,特别第二种，简直神一样！！！！！
1th:构造最小生成树。
我们提取所有的边出来按边排序，因为每次我们知道边的权值>0，
之后每次把边加入集合中，不断构造，类似 kruskal算法，构造出边后
再对每个点进行整张图的DFS求距离
复杂度O(N^2lgN)：对所有边排序的复杂度。
#include<bits/stdc++.h> #define N 2222
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f
int n;
int f[N],vis[N];
int a[N][N]; struct node
{
int u,v,w;
node(int uu,int vv,int ww):u(uu),v(vv),w(ww){}
}; vector<pair<int,int> > G[N];
vector<node> edge; int find(int x)
{if (f[x]!=x) return f[x]=find(f[x]);} int cmp(node a,node b){return a.w<b.w;} ll dis[N];
void dfs(int x)
{
vis[x]=;
// cout<<dis[x]<<" ";
for (int i=;i<G[x].size();i++)
{
int v=G[x][i].first;
int w=G[x][i].second;
if (vis[v]) continue;
dis[v]=dis[x]+w;
dfs(v);
}
} int solve()
{
for (int i=;i<n;i++)
for (int j=i+;j<=n;j++)
edge.push_back(node(i,j,a[i][j])); for (int i=;i<=n;i++) f[i]=i; sort(edge.begin(),edge.end(),cmp);
int t=edge.size();
for (int i=;i<t;i++)
{
int x=edge[i].u;
int y=edge[i].v;
int tx=find(x);
int ty=find(y);
if (tx!=ty)
{
f[tx]=ty;
G[x].push_back(make_pair(y,edge[i].w));
G[y].push_back(make_pair(x,edge[i].w));
}
} for (int i=;i<=n;i++)
{
memset(vis,,sizeof(vis));
memset(dis,,sizeof(dis));
dfs(i); for (int j=;j<=n;j++)
if (dis[j]!=a[i][j])
{
return ;
}
}
return ;
} int main()
{ scanf("%d",&n);
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
scanf("%d",&a[i][j]); for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
{
if (a[i][j]!=a[j][i]||i==j&&a[i][j]!=)
{
puts("NO");
return ;
}
if (i!=j&&a[i][j]==)
{
puts("NO");
return ;
}
} if (solve()) puts("YES");
else puts("NO");
return ;
}
代码可能更好说明思路，关键一点是：我们每次把最短的边加入集合。我们确定这是一颗最小生成树！所以加边次序是和MST是一样的。
第二种做法不得不佩服！1
这个特种点很难在比赛中发现啊
关键点：我们知道一个点到其他所有点都有一条最小距离的边--假设A到其他点最小距离的点是B，A-B一定是直接连接的。假设距离是X。
然后假设一个点C，C到B点要么比C到A点近X，要么C到A点远X。具体可以画图。
通过这个方法可以判断数据是否合法！
代码超级短
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 2222 int a[N][N];
int n;
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
scanf("%d",&a[i][j]); //预处理判断
int flag=;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
{
if (i!=j&&a[i][j]==) flag=;
if (i==j&&a[i][j]!=) flag=;
if (i!=j&&a[i][j]!=a[j][i]) flag=;
} if (flag)
{
puts("NO");
return ;
} for (int i=;i<=n;i++)
{
int inf= ;//初始的值要比较大些
int pos=-;
for (int j=;j<=n;j++){
if (i==j) continue;
if (a[i][j]<inf)
{
inf =a[i][j];
pos=j;
}
}
for (int j=;j<=n;j++)
{
if (i==j||j==pos) continue;
if (abs(a[i][j]-a[pos][j])!=inf)
{
puts("NO");
return ;
}
}
} puts("YES");
return ;
} 后面的基本是水体了：
C：贪心：
从第一的判断每次找合理值，矛盾就错误！
B:
我是用贪心的做法！
想想我们最后电梯还是要回到第一层！对吧！
也要走到最高层，当前有人想去的最高层！
那么我们每次把前K高层的先送上去！就能满足答案最小！
#define N 111111
using namespace std; int a[];
int cmp(int x,int y)
{
return x>y;
}
int main()
{
int n,k;
cin>>n>>k; for (int i=;i<=n;i++) cin>>a[i];
sort(a+,a+n+,cmp);
int ans=;
for (int i=;i<=n;i+=k)
ans+=(a[i]-)*; cout<<ans<<endl;
return ;
复杂度O(N^2);时间600MS;这是快