CF 253C(找中转行)

Posted on 8 12 月, 2012 by nike0good

文本编辑器有n行，每行k个字符（显然光标有k+1个位置，标记为1..k+1.

有4个操作：

"Up": 光标将向上移1行，列不变。如果上一行字符太少，则光标跑到行末。

"Down":
光标将向下移1行，列不变。如果上一行字符太少，则光标跑到行末。

"Right": 光标向右移1格，操作不能在行末进行。

"Left":
光标向左移1格，操作不能在行首进行。

求出把光标从 (r₁, c₁) 移向(r₂, c₂)最小步数.

Input

第一行一个整数 n (1 ≤ n ≤ 100) . 第二行 n个整数a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁵),
表示每行字符数. 第三行4个整数 r₁, c₁, r₂, c₂ (1 ≤ r₁, r₂ ≤ n, 1 ≤ c₁ ≤ a_r₁ + 1, 1 ≤ c₂ ≤ a_r₂ + 1).

Output

输出最小步数

Sample test(s)

input
4
2 1 6 4
3 4 4 2

output
3

input
4
10 5 6 4
1 11 4 2

output
6

input
3
10 1 10
1 10 1 1

output
3

Note

第一组数据若为

123

123s567

1t345

则最小操作为 "Left", "Down", "Left".

显然除了直接移(先行后列）外，

唯一减少操作数的方法便是向中间以外的行数移，以求降低列的移动数。

一定要注意不是挪到每行直接取abs(行尾-c2)的，因为可能会有往返行尾的路上有更小的，直接取行尾可能拉近它和c2的距离，但是这种操作是不可行的。

#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN (10000+100)
int a[MAXN],n;
int abs2(int a,int b)
{
	if (a<b) return b-a;
	else return a-b;
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	int r1,c1,r2,c2;
	scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
	int mi=c1,ans=0,tans=1000000000;
	if (r1<r2)
	{
		ans=r2-r1;
		for (int i=r1+1;i<=r2;i++) mi=min(mi,a[i]+1);
		tans=min(tans,ans+abs(mi-c2));
		for (int i=r1-1,cost=2,mii=mi;i>=1;i--,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
		for (int i=r2+1,cost=2,mii=mi;i<=n;i++,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
	}
	else
	{
		ans=r1-r2;
		for (int i=r1-1;i>=r2;i--) mi=min(mi,a[i]+1);
		tans=min(tans,ans+abs(mi-c2));
		for (int i=r2-1,cost=2,mii=mi;i>=1;i--,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
		for (int i=r1+1,cost=2,mii=mi;i<=n;i++,cost+=2)
		{
			mii=min(mii,a[i]+1);
			tans=min(tans,ans+cost+abs(mii-c2));
		}
	}
	cout<<tans<<endl;
	return 0;
}

CF 253B(队列上维护2个指针后移)

Posted on 8 12 月, 2012 by nike0good

小明做实验，测了n次结果，因为误差，这些结果不一样。

至少修改多少结果，才能使最大的结果不超过最小的结果的2倍？

Input

第一行一个整数 n (2 ≤ n ≤ 10⁵)，第二行有n个数c₁, c₂, ..., c_n表示结果(1 ≤ c_i ≤ 5000)

Output

输出一个整数，表示最小修改次数。

Sample test(s)

input
6
4 5 3 8 3 7

output
2

input
4
4 3 2 4

output
0

Note

第1个数据删除8，7，第二个数据本身就满足条件。

排序，从小到大枚举最小数，并把后指针挪向最大的不用修改的数进行统计即可。

#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
#define MAXN (100000+100)
int a[MAXN];
int n;
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);

	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	a[n+1]=1000000;
//	for (int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
	int t=1,ans=0;
	for (int h=1;h<=n;h++)
	{
		while (a[h]*2>=a[t+1]) t++;
		ans=max(ans,t-h+1);
	}
	cout<<n-ans<<endl;

}

CF 253A(最大间隔相异队列)

Posted on 8 12 月, 2012 by nike0good

有n个男孩和m个女孩排队，我们希望相邻的2个孩子性别尽可能不同。

请帮助它们排队。

Input

第1行有2个整数 n,m (1 ≤ n, m ≤ 100).

Output

请输出一行它们排队的队列，B表示男孩,G表示女孩.

输出任意一种方案即可。

Sample test(s)

input
3 3

output
GBGBGB

input
4 2

output
BGBGBB

Note

In the first sample another possible answer is BGBGBG.

In the second sample answer BBGBGB is also optimal.

分成2种情况考虑-男多女少和女多男少

考虑以下2种情况：

BGBGBB

BGBGGG-->GBGBGG 显然后面间隔较多

Program Boys;
var
   n,m,i:longint;
begin
   assign(input,'input.txt');
   assign(output,'output.txt');
   reset(input);
   rewrite(output);
   read(n,m);
   if n<m then
   begin
      for i:=1 to n do write('GB');
      for i:=n+1 to m do write('G');
   end
   else
   begin
      for i:=1 to m do write('BG');
      for i:=m+1 to n do write('B');
   end;
   writeln;

   close(input);close(output);
end.

ZOJ 1576(稳定婚姻系统-重名)

Posted on 8 12 月, 2012 by nike0good

Marriage is Stable

Time Limit: 5 Seconds
Memory Limit: 32768 KB Special Judge

Albert, Brad, Chuck are happy bachelors who are in love with Laura, Marcy, Nancy. They all have three choices. But in fact, they do have some preference in mind. Say Albert, he likes Laura best, but that doesn't necesarily mean Laura likes him. Laura likes
Chuck more than Albert. So if Albert can't marry Laura, he thinks Nancy a sensible choice. For Albert, he orders the girls Laura > Nancy > Marcy.

For the boys:

Albert: Laura > Nancy > Marcy
Brad: Marcy > Nancy > Laura
Chuck: Laura > Marcy > Nancy

For the girls:

Laura: Chuck > Albert > Brad
Marcy: Albert > Chuck > Brad
Nancy: Brad > Albert > Chuck

But if they were matched randomly, such as

Albert <-> Laura
Brad <-> Marcy
Chuck <-> Nancy

they would soon discover it's not a nice solution. For Laura, she likes Chuck instead of Albert. And what's more, Chuck likes Laura better than Nancy. So Laura and Chuck are likely to come together, leaving poor Albert and Nancy.

Now it's your turn to find a stable marriage. A stable marriage means for any boy G and girl M, with their choice m[G] and m[M], it will not happen that rank(G, M) < rank(G, m[G]��and rank(M, G) < rank(M, m[M]).

Input

Each case starts with an integer n (1 <= n <= 500), the number of matches to make.

The following n lines contain n + 1 names each, the first being name of the boy, and rest being the rank of the girls.

The following n lines are the same information for the girls.

Process to the end of file.

Output

If there is a stable marriage, print n lines with two names on each line. You can choose any one if there are multiple solution. Print "Impossible" otherwise.

Print a blank line after each test.

Sample Input

3
Albert Laura Nancy Marcy
Brad Marcy Nancy Laura
Chuck Laura Marcy Nancy
Laura Chuck Albert Brad
Marcy Albert Chuck Brad
Nancy Brad Albert Chuck

Sample Output

Albert Nancy
Brad Marcy
Chuck Laura

这题就是稳定婚姻系统，

注意有同名的男女。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
#include<queue>
#include<iostream>
#include<map>
#include<string>
using namespace std;
#define MAXN (2000+10)
int n;
queue<int> q;
map<string,int> hpos_male,hpos_female;

int female_like[MAXN][MAXN];  //SIS
int male_like[MAXN][MAXN];    //SSI
int match[MAXN];
string a[MAXN];
int main()
{
//	freopen("zoj1576.in","r",stdin);
	while (scanf("%d",&n)!=EOF)
	{
		hpos_male.clear();
		hpos_female.clear();
		memset(match,0,sizeof(match));
		int size=n+1;
		for (int i=1;i<=n;i++)
		{
			cin>>a[i];hpos_male[a[i]]=i; q.push(i);
			for (int j=1;j<=n;j++)
			{
				string s;
				cin>>s;
				if (i==1)
				{
					hpos_female[s]=size;
					a[size]=s;
					size++;
				}
				male_like[i][j]=hpos_female[s];
			}
		}
		for (int i=n+1;i<=2*n;i++)
		{
			string sg;
			cin>>sg;
			for (int j=1;j<=n;j++)
			{
				string s;
				cin>>s;
				female_like[hpos_female[sg]][hpos_male[s]]=j;
			}
		}
		/*
		for (int i=n+1;i<=2*n;i++)
		{
			for (int j=1;j<=n;j++)
				cout<<female_like[make_pair(a[i],a[j])]<<' ';
			cout<<endl;
		}
		*/
		while (!q.empty())
		{
			int now=q.front();
			q.pop();
			for (int j=1;j<=n;j++)
			{
				int v=male_like[now][j];
				if (!match[v])
				{
					match[now]=v;match[v]=now;//cout<<now<<' '<<v<<endl;
					break;
				}
				else if (female_like[v][match[v]]>female_like[v][now])
				{
					q.push(match[v]);
					match[match[v]]=0;
					match[now]=v;match[v]=now;//cout<<now<<' '<<v<<endl;
					break;
				}
			}
		}
		for (int i=1;i<=n;i++)
		{
			cout<<a[i]<<' '<<a[match[i]]<<endl;
		}
		printf("n");
	}
	return 0;
}

一	二	三	四	五	六	日
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

nike0good

有所作为是人生的最高境界

Daily Archives: 8 12 月, 2012

CF 253C(找中转行)

CF 253B(队列上维护2个指针后移)

CF 253A(最大间隔相异队列)

ZOJ 1576(稳定婚姻系统-重名)