网站app的作用/江门网站定制多少钱

题意：给定n个点（1-n），围成一个圈。然后给出p对点对，表示这两个点要进行交谈。交谈的方式是使得这两个点之间连通，但是只能在相邻的两个点之间连线。问完成任务，最少需要多少条线。比如1和n-1要交谈，那么在1和n之间以及n和n-1之间连线即可。

思路：暴力枚举+优化。首先容易确定的一点是肯定不需要围成一个圈，因为最坏情况连接n-1条边就可以使得所有牛之间都能够交谈。那么接下来的思路就是枚举这个断开的边所在的位置，相当于将圈拉成了一条线，然后处理p个点对，此时每个点对的连线方案就确定了。具体的方法，如果i和j要交谈(i<j)，那么开一个数组令t[i] = j，表示i和j之间所有边都要连上。然后从左到右扫一遍求一共的加边数量即可。这样的复杂度是O(np)=O(10000000)。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 0x3fffffff
#define clr(s,t) memset(s,t,sizeof(s))
#define N 1005
int n,m;
int s[10005][2],t[N<<1];
int main(){int i,j,a,b,res,now;scanf("%d %d",&n,&m);for(i = 1;i<=m;i++)scanf("%d %d",&s[i][0],&s[i][1]);for(i = 1,res=INF;i<=n;i++){clr(t, 0);now = 0;for(j = 1;j<=m;j++){a = s[j][0];if(a<i)//因为小于i的去到了右边a += n;b = s[j][1];if(b<i)b+=n;if(a>b)swap(a,b);t[a] = max(t[a],b);}for(j = a = i;j<i+n;j++)if(t[j] > a){now += t[j] - max(a,j);a = t[j];}res = min(res,now);}printf("%d\n",res);return 0;
}