算法竞赛入门经典（第八章）

习题8-1 Uva1149　　11.8　　

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
//	freopen("in.txt","r",stdin);
	int T;
	cin>>T;
	while(T--)
	{
	    int n, m, mi;
	    int w[100005];
	    int num;
	    int l, r;
	    cin>>n>>m;
	    for(int i = 1; i <= n; i++)
	    {
	        cin>>w[i];
	    }
	    sort(w+1, w+n+1);
	    l = 1 , r = n;
	    num = 0;
	    while(l<=r)
	    {
	        mi = m - w[r--];
	        if(r==l)
	        {
	        	num++;
	        	break;
	        }
	        if(mi - w[l] >= 0)    	l++;
			num++;
	    }
	    cout<<num<<endl;		
	}

    return 0;
} 

　　

　　习题8-2 Uva1610　　11.8

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
string qz(string a, string b)
{
	string ans;
	int len = min(a.length(), b.length());
	if(a==b)
	{
		return a;
	}	
	
	for(int i = 0; i < len; i++)
	{
		if(a[i] == b[i])	ans = ans + a[i];
		else
		{
			ans = ans + (char)(a[i] + 1);
			return ans;
		}
	}
	return a;
} 
int main()
{
	freopen("in.txt","r",stdin);
	string stc[105];
	int n; 
	cin>>n;
	for(int i = 1; i <= n; i++)
		cin>>stc[i];
	sort(stc + 1, stc + n + 1); 
	if(n%2)
	{
		n = n / 2;
		cout<<stc[n]<<endl;
	}
	else
	{
		string ans = qz(stc[n/2],stc[n/2+1]);
		cout<<ans<<endl;
	}
	return 0;
} 

　　习题8-3 Uva12545　　11.8

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int main()
{
	freopen("in.txt","r",stdin);
	int n0, n1, nx;
	n0 = n1 = nx = 0;
	char s[105];
	char t[105];
	cin>>s>>t;
	int len = strlen(s);
	for(int i = 0; i <= len; i++)
	{
		if(s[i] != t[i])
		{
			switch(s[i])
			{
				case '1':	n1++;	break;
				case '0':	n0++;	break;
				case '?':	nx++; 	break;
			}
		}
	}
	cout<<nx+max(n1,n0)<<endl;
	return 0;
} 

　　习题8-4 Uva11491　　11.8

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int main()
{
	freopen("in.txt","r",stdin);
	char num[100005];
	int n, m, d;
	cin>>n>>d;
	cin>>num;
	m = 0;
	for(int i = 0; i <= d + 1; i++)
	{
		if(i != d + 1)
		{
			if(num[i] > num[m])		m = i;
		}
		else
		{
			if(d == n)	break;
			cout<<num[m];
			i = m;
			m = i + 1;
			d++;
			
		}
	}
	return 0;
} 

　　习题8-6 Uva1611　　11.9

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
using namespace std;
#define N 10100
int num[N];
int cur[N];
int li[N], ri[N];
int stp = 0;
void swapk(int l, int r)
{
    li[stp] = l;
    ri[stp++] = r;
    int k = (l + r + 1)>>1;
    for(int i = k; i <= r; i++)
    {
        int z = num[l];
        num[l] = num[i];
        num[i] = z;
        cur[num[i]] = i;
        cur[num[l]] = l;
        l++;
    }
    return;
}

int main() {
    freopen("in.txt","r",stdin);
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        cin>>num[i];
        cur[num[i]] = i;
    }
    for(int i = 1; i <= n; i++)
    {

        if(cur[i] == i) continue;
        else if(cur[i]*2 <= i+n)
        {
            swapk(i, cur[i] - i - 1 + cur[i]);
        }
        else
        {
            if((i%2)^(n%2))
            {
                swapk(i, n);
            }
            else
            {
                swapk(i, n-1);
            }
            i--;
        }
    }
    cout<<stp<<endl;
    for(int i = 0; i < stp; i++)
        cout<<li[i]<<" "<<ri[i]<<endl;
    for(int j  = 1; j <= n; j++)
        cout<<num[j]<<" ";
    cout<<endl;
    return 0;
}

　　习题8-7 Uva11925　　11.10

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
vector<int>num;
bool pd(int n)
{
	for(int i = 0; i < n; i++)
	{
		if(num[i] != i+1)	return true;
	}
	return false;
} 
int main() {
    freopen("in.txt","r",stdin);
    int n, m; 
    int h=0;
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
    	cin>>m;
    	num.push_back(m);
    }
    while(pd(n))
    {
    	int cur = 0;
		if(num[1] < num[0])	cur = 1;
		if(num[1]==1 && num[0]==n)	cur = 0;
		if(num[1]==n && num[0]==1)	cur = 1;
		if(cur)	cout<<"1";
		m = num[cur];
    	num.erase(num.begin()+cur);
    	cout<<"2";
    	num.push_back(m);
//    	cout<<endl;
//    	for(int i = 0; i < n; i++)
//    		cout<<num[i]<<" ";
//    	cout<<endl;
    }
    cout<<endl;
    return 0;
}

　　习题8-11 Uva1615　　11.10

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
	double x, y;
}dot[100005];
bool cmp(node a, node b)
{
	return a.y<b.y;
}
int main()
{
	freopen("in.txt","r",stdin);
    int n; 
    double d;
    cin>>n;
    for(int i = 0; i < n; i++)
		cin>>dot[i].x>>dot[i].y;
	
	for(int i = 0; i < n; i++)
	{
		dot[i].x -= sqrt(d*d - dot[i].y*dot[i].y);
		dot[i].y += sqrt(d*d - dot[i].y*dot[i].y);
	}
	sort(dot, dot+n, cmp);
	int cur = 0;
    int tmp = 1;
	for(int i = 0; i < n; i++)
    {
    	if(dot[i].x > dot[cur].y)
    	{
    		cur = i;
    		tmp++;
    	}
    }
    cout<<tmp<<endl;
    return 0;
}

　　习题8-13 Uva10570　　11.10

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
int tmp[1005];
int num[1005];
int cur[1005];
int n, m;
int main()
{
	freopen("in.txt","r",stdin);
	m = 0; 
	cin>>n;
	for(int i = 1; i <= n; i++)
	{
		cin>>num[i];
	}
	int ans = 1000;
	for(int i = 1; i <= n; i++)
	{
		int key = 0;
		for(int j = 1; j <= n; j++)
		{
			tmp[j] = num[j + i - 1];
			cur[tmp[j]] = j;
		}
		for(int j = 1; j <= n; j++)
		{
			if(cur[j] != j)
			{
				cur[tmp[j]] = cur[j];
				key++;
			}
		}
		if(key < ans)	ans = key;
	}
	cout<<ans;
	return 0;
} 

　　习题8-14 Uva10570　　11.10

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
struct node
{
	int x, y;
}num[100005];
int n, m = 0;
bool cmp(node a, node b)
{
	return a.x<b.x;
}

bool pd(int x)
{
	int cur = 0;
	for(int i = 1; i <= n; i++)
	{
		if(cur < num[i].x)	cur = num[i].x + x;
		else 	cur += x;
		if(cur > num[i].y)	return false;
	}
	return true;
}

int main()
{
	freopen("in.txt","r",stdin);
	cin>>n;
	for(int i = 1; i <= n; i++)
	{
		cin>>num[i].x>>num[i].y;
		num[i].x*=2;
		num[i].y*=2;
		m = m > (num[i].y - num[i].x)?m:(num[i].y - num[i].x);
	}
	sort(num+1, num+1+n, cmp);
	int l = 0;
	int r = m;
	while(r - l != 1)
	{
		if(pd((l+r)>>1))	l = (l+r)>>1;
		else	r = (l+r)>>1;
	}
	cout<<l<<endl;
	return 0;
} 

习题8-21 Uva1621　　11.13　　

/*感谢SLO，提供的代码，我菜是想了好久都没想到好办法，得到指点真是太好了
构造的题感觉和数学题目差不多了，都是要找一种方法来解决问题
这道题目就是先把3步的走完，然后在走1,2步的，牛逼啊
深受影响啊
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int ans[5005*3],n;
int main(){

    int T;
    while(scanf("%d",&T)==1)while(T--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        n=0;
        int p=0;
        ans[n++]=0;
        if((c+1)%3==0){
            for(int i=0;i<(c+1)/3;++i)  ans[n++]=(p+=3);
            ans[n++]=--p;--a;
            for(int i=1;i<(c+1)/3;++i)  ans[n++]=(p-=3);
            ans[n++]=--p;--a;
            for(int i=0;i<(c+1)/3;++i)  ans[n++]=(p+=3);
        }
        if((c+2)%3==0){
            for(int i=0;i<(c+2)/3;++i)  ans[n++]=(p+=3);
            ans[n++]=(p-=2);--b;
            for(int i=1;i<(c+2)/3;++i)  ans[n++]=(p-=3);
            ans[n++]=++p;--a;
            for(int i=1;i<(c+2)/3;++i)  ans[n++]=(p+=3);
            ans[n++]=(p+=2);--b;
        }
        if(c%3==0){
            for(int i=0;i<c/3;++i)  ans[n++]=(p+=3);
            ans[n++]=++p;--a;
            for(int i=0;i<c/3;++i)  ans[n++]=(p-=3);
            ans[n++]=++p;--a;
            for(int i=0;i<c/3;++i)  ans[n++]=(p+=3);
        }
        for(;a>1;--a)ans[n++]=++p;
        for(int i=0;i<(b+1)/2;++i)  ans[n++]=(p+=2);
        if(b%2==0)ans[n++]=++p;
        else ans[n++]=--p;
        for(int i=b&1;i<(b+1)/2;++i)    ans[n++]=(p-=2);
        for(int i=0;i<n;++i)printf(i<n-1?"%d ":"%d
",ans[i]);
    }
    return 0;
}

习题8-24 Uva10366　　11.12

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <windows.h>
using namespace std;
int l, r; 
int ml, mr;
int xl, xr;
int li[1005], ri[1005];
void sscanf()
{
	int id;
	ml = mr = 0;
	for(int i = l; i <= r; i+=2)
	{
		if(i < 0)
		{
			id = (-i)/2;
			scanf("%d",&li[id]);
			if(li[id] >= ml)
			{
				ml = li[id];
				xl = id;
			}
		}
		else{
			id = i/2;
			scanf("%d",&ri[id]);
			if(ri[id] > mr)
			{
				mr = ri[id];
				xr = id;
			}
		}
	}
}

int solve()
{
	int k, tmp;
	l = (-l)/2;
	r = r/2;
	int al, ar;
	if(ml == mr)
	{
		k = 0;
		tmp = li[l];
		for(int i = l; i > xl; i--)
		{
			k+=tmp;
			tmp = max(tmp,li[i-1]);
		}
		al = k;
		tmp = ri[r];
		k = 0;
		for(int i = r; i > xr; i--)
		{
			k+=tmp;
			tmp = max(tmp,ri[i-1]);
		}
		ar = k;
		return (xl+xr+1)*ml+min(ar,al);
	}
	else if(ml > mr)
	{
		tmp = ri[r];
		k = 0;
		for(int i = r; i > 0; i--)
		{
			k+=tmp;
			tmp = max(tmp,ri[i-1]);
		}
		for(int i = 0; i < l; i++)
		{
			k+=tmp;
			if(li[i]>tmp)	break;
		}
		return k;
	}	
	else
	{
		tmp = li[l];
		k = 0;
		for(int i = l; i > 0; i--)
		{
			k+=tmp;
			tmp = max(tmp,li[i-1]);
		}
		for(int i = 0; i < r; i++)
		{
			k+=tmp;
			if(ri[i]>tmp)	break;
		}
		return k;
	}	
}

int main()
{
	freopen("in.txt","r",stdin);
	while(cin>>l>>r)
	{
		sscanf();
		int ans = solve();
		cout<<ans<<endl;
	}
	return 0;
} 

　　习题8-23 Uva1623　　11.20

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge
{
	int s, t;
}num[1000005];
int link[100005];
int tmp[100005];
bool cmp(edge a, edge b)
{
	if(a.s == b.s)	return a.t<b.t;
	return a.s < b.s;
}
int main()
{
	freopen("in.txt","r",stdin);
	int T;
	cin>>T;
	while(T--)
	{
		memset(link, 0, sizeof(link));
		bool flag = false;
		int n, m, mi = 0;
		int ni = 0;
		cin>>n>>m;
		for(int i = 1; i <= m; i++)
		{
			cin>>tmp[i];
			if(tmp[i])
			{
				num[mi].s = link[tmp[i]];
				num[mi].t = i;
				mi++;
				link[tmp[i]] = i;
			}
		}
		sort(num, num+mi, cmp);
		for(int i = 1; i <= m; i++)
		{
			if(tmp[i])				continue;
			if(tmp[i] < num[ni].s)	continue;
			if(ni == mi)			break;
			if(i > num[ni].s && i < num[ni].t)
			{
				tmp[i] = 0 - tmp[num[ni].t];
				ni++;
			}
			else
			{
				flag = true;
				break;
			}
		}
		if(flag || ni != mi)	cout<<"NO"<<endl;
		else
		{
			for(int i = 1; i <= m; i++)
			{
				if(tmp[i] <= 0)	cout<<0-tmp[i]<<" ";
			}
			cout<<endl;
		}		
	}

	return 0;	
}

　　习题8-18 Uva1619　　11.20

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int li[100005];
int ri[100005];
int tmp[100005];
int sum[100005];
int main()
{
	freopen("in.txt","r",stdin);
	int n, maxx = 0;
	int al, ar;
	cin>>n;
	for(int i = 1; i <= n; i++)
	{
		cin>>tmp[i];
		sum[i] = sum[i-1] + tmp[i];
	}
	for(int i = 1; i <= n; i++)
	{
		int l, r;
		l = r = i;
		while(tmp[l-1] >= tmp[i] && l > 1)	l--;
		li[i] = l;
		while(tmp[r+1] >= tmp[i] && r < n)	r++;
		ri[i] = r;
	}
	for(int i = 1; i <= n; i++)
	{
		
		if(maxx < (tmp[i] * (sum[ri[i]] - sum[li[i]-1])))
		{
			al = li[i];
			ar = ri[i];
			maxx = (tmp[i] * (sum[ri[i]] - sum[li[i]-1]));
		}
	}
	cout<<maxx<<endl<<al<<" "<<ar<<endl;;
	return 0;	
}