2017-07-14 02:17:40 my_sunshine26 阅读数 601
  • redis高并发处理由浅入深(备java基础,javaee课程)

    Redis是一款依据BSD开源协议发行的高性能Key-Value存储系统(cache and store)。 命令主要分以下几部分关键字(Keys) 字符串(String) 哈希(Hashs) 列表(Lists) 集合(Sets) 有序集合(Sorted Sets)HyperLogLog 发布/订阅(Pub/Sub) 事务(Transactions) 脚本(Scripting)

    11828 人正在学习 去看看 任亮


D. Office Keys

time limit per test 2 seconds

memory limit per test     256 megabytes

There aren people and k keys on a straight line. Every person wants to get to theoffice which is located on the line as well. To do that, he needs to reach somepoint with a key, take the key and then go to the office. Once a key is takenby somebody, it couldn't be taken by anybody else.

You are to determine the minimum time needed for alln people to get to the office with keys.Assume that people move a unit distance per1 second. If two people reach a key atthe same time, only one of them can take the key. A person can pass through apoint with a key without taking it.

Input

The first line contains three integersn,k and p (1 ≤ n ≤ 1 000,n ≤ k ≤ 2 000,1 ≤ p ≤ 109) — the number of people,the number of keys and the office location.

The second line containsn distinct integers a1, a2, ..., an (1 ≤ ai ≤ 109) — positions in whichpeople are located initially. The positions are given in arbitrary order.

The third line containsk distinct integers b1, b2, ..., bk (1 ≤ bj ≤ 109) — positions of the keys.The positions are given in arbitrary order.

Note that there can't be more than one person or more than onekey in the same point. A person and a key can be located in the same point.

Output

Printthe minimum time (in seconds) needed for alln to reach the office with keys.

Examples

Input

2 4 50
20 100
60 10 40 80

Output

50

Input

1 2 10
11
15 7

Output

7

Note

In the first example the person located at point20 should take the key located at point 40 and go with it to the office locatedat point 50. He spends 30 seconds. The person located at point 100 can take the key located at point 80 and go to the office with it. Hespends 50seconds. Thus, after 50 seconds everybody is in office with keys.



【题意】在一条直线上,有n个人和k把钥匙,还有一个公司,问所有人都拿到一把钥匙(一个钥匙只能被拿一次)然后再到公司的最短时间是多少?

【思路1】由于要尽可能使每个人拿到距离自己最近的钥匙,我们先把所有人根据位置排序,把所有钥匙根据位置排序,然后二分答案,判断某一个值是否满足条件,具体判断过程见代码,每次尽量取左边的钥匙。


二分时注意使用long long 类型


#include <cstdio>
#include <map>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)

typedef long long ll;
const int maxn= 2005;
const int mod = 20090717;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;

int n,k,p;
ll a[maxn];
ll b[maxn];
bool vis[maxn];

bool judge(ll limit)
{
    int num=0;
    mst(vis,0);
    for(int i=0;i<k;i++)
    for(int j=0;j<n;j++)
    {
        if(vis[j]) continue;
        if(abs(b[i]-a[j])+abs(b[i]-p)<=limit)
        {
            vis[j]=true;
            num++;
            break;
        }
    }
    return num==n;
}

int main()
{
    scanf("%d%d%d",&n,&k,&p);
    for(int i=0;i<n;i++)
    {
        scanf("%I64d",&a[i]);
    }
    for(int i=0;i<k;i++)
    {
        scanf("%I64d",&b[i]);
    }
    sort(a,a+n);
    sort(b,b+k);
    ll l=0,r=2e9+5;
    ll ans;
    while(l<=r)
    {
        ll m=(l+r)/2;
        if(judge(m))
        {
            r=m-1;
            ans=m;
        }
        else l=m+1;
    }
    printf("%I64d\n",ans);
    return 0;
}


【思路2】用dp[i][j]表示前i个人在前j把钥匙中都拿到了钥匙并到达公司的最短时间。(所有人最短时间里的最大值)

可以写出状态转移方程:

dp[i][j]=min(dp[i][j-1],max(dp[i-1][j-1]+abs(pos[j]-p)))

最终结果便是dp[n][k].


#include <cstdio>
#include <map>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%I64d",&T);while(T--)

typedef long long ll;
const int maxn= 2005;
const int mod = 20090717;
const ll INF = 1e15;
const double eps = 1e-6;

int n,k;
ll p;
ll a[maxn];
ll b[maxn];
ll dp[maxn][maxn];


int main()
{
    scanf("%d%d%I64d",&n,&k,&p);
    for(int i=1;i<=n;i++)
    {
        scanf("%I64d",&a[i]);
    }
    for(int i=1;i<=k;i++)
    {
        scanf("%I64d",&b[i]);
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+k);
    mst(dp,0);
    for(int i=1;i<=n;i++)
    for(int j=i;j<=k;j++)
    {
        if(i==j)
            dp[i][j]=max(dp[i-1][j-1],abs(a[i]-b[j])+abs(b[j]-p));   //由j>=i,故i==j时特判
        else dp[i][j]=min(dp[i][j-1],max(dp[i-1][j-1],abs(a[i]-b[j])+abs(b[j]-p)));
    }
    printf("%I64d\n",dp[n][k]);
    return 0;
}





2017-12-03 19:59:32 chengyq116 阅读数 419
  • redis高并发处理由浅入深(备java基础,javaee课程)

    Redis是一款依据BSD开源协议发行的高性能Key-Value存储系统(cache and store)。 命令主要分以下几部分关键字(Keys) 字符串(String) 哈希(Hashs) 列表(Lists) 集合(Sets) 有序集合(Sorted Sets)HyperLogLog 发布/订阅(Pub/Sub) 事务(Transactions) 脚本(Scripting)

    11828 人正在学习 去看看 任亮

Microsoft Office Visio 2010 -  hot keys

1. hot keys
←/↑/→/↓:移动所选形状
Shift + ←/↑/→/↓:微移所选形状
Ctrl + ←/↑/→/↓:移动画布

 

2017-07-15 11:35:37 Jelly_acm 阅读数 293
  • redis高并发处理由浅入深(备java基础,javaee课程)

    Redis是一款依据BSD开源协议发行的高性能Key-Value存储系统(cache and store)。 命令主要分以下几部分关键字(Keys) 字符串(String) 哈希(Hashs) 列表(Lists) 集合(Sets) 有序集合(Sorted Sets)HyperLogLog 发布/订阅(Pub/Sub) 事务(Transactions) 脚本(Scripting)

    11828 人正在学习 去看看 任亮
D. Office Keys
time limit per test
 2 seconds
memory limit per test
 256 megabytes
input
 standard input
output
 standard output

There are n people and k keys on a straight line. Every person wants to get to the office which is located on the line as well. To do that, he needs to reach some point with a key, take the key and then go to the office. Once a key is taken by somebody, it couldn't be taken by anybody else.

You are to determine the minimum time needed for all n people to get to the office with keys. Assume that people move a unit distance per 1 second. If two people reach a key at the same time, only one of them can take the key. A person can pass through a point with a key without taking it.

Input

The first line contains three integers nk and p (1 ≤ n ≤ 1 000n ≤ k ≤ 2 0001 ≤ p ≤ 109) — the number of people, the number of keys and the office location.

The second line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ 109) — positions in which people are located initially. The positions are given in arbitrary order.

The third line contains k distinct integers b1, b2, ..., bk (1 ≤ bj ≤ 109) — positions of the keys. The positions are given in arbitrary order.

Note that there can't be more than one person or more than one key in the same point. A person and a key can be located in the same point.

Output

Print the minimum time (in seconds) needed for all n to reach the office with keys.

Examples
input
2 4 50
20 100
60 10 40 80
output
50
input
1 2 10
11
15 7
output
7
Note

In the first example the person located at point 20 should take the key located at point 40 and go with it to the office located at point 50. He spends 30 seconds. The person located at point 100 can take the key located at point 80 and go to the office with it. He spends 50seconds. Thus, after 50 seconds everybody is in office with keys.

——————————————————————————————————
题目的意思是在一条直线上给出n个人的位置和m把钥匙的位置和一个办公室位置,求每个人拿了钥匙进办公室最少时间,每把钥匙只能被一个人拿
思路:先排序,再二分时间,验证能否在这个时间都进办公室,验证时可以贪心尽可能让每个人拿左边钥匙

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
 
using namespace std;
 
#define LL long long
const int INF = 0x3f3f3f3f;
#define MAXN 2000010
 
LL a[100005],b[100005];
LL p;
int n,m;
bool ok(LL mid)
{
    int l=0,r=0;
    while(l<n&&r<m)
    {
        if(fabs(a[l]-b[r])+fabs(p-b[r])<=mid)
            l++,r++;
        else
            r++;
    }
    if(l==n) return 1;
    return 0;
}
 
int main()
{
 
    scanf("%d%d%lld",&n,&m,&p);
    for(int i=0; i<n; i++)
        scanf("%lld",&a[i]);
    for(int j=0; j<m; j++)
        scanf("%lld",&b[j]);
    sort(a,a+n);
    sort(b,b+m);
    LL l=0,r=100000000000;
    LL ans;
    while(l<=r)
    {
        LL mid=(l+r)/2;
        if(ok(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}

2017-07-24 18:13:18 fsmm_blog 阅读数 279
  • redis高并发处理由浅入深(备java基础,javaee课程)

    Redis是一款依据BSD开源协议发行的高性能Key-Value存储系统(cache and store)。 命令主要分以下几部分关键字(Keys) 字符串(String) 哈希(Hashs) 列表(Lists) 集合(Sets) 有序集合(Sorted Sets)HyperLogLog 发布/订阅(Pub/Sub) 事务(Transactions) 脚本(Scripting)

    11828 人正在学习 去看看 任亮
A. Office Keys
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are n people and k keys on a straight line. Every person wants to get to the office which is located on the line as well. To do that, he needs to reach some point with a key, take the key and then go to the office. Once a key is taken by somebody, it couldn't be taken by anybody else.

You are to determine the minimum time needed for all n people to get to the office with keys. Assume that people move a unit distance per 1 second. If two people reach a key at the same time, only one of them can take the key. A person can pass through a point with a key without taking it.

Input

The first line contains three integers n, k and p (1 ≤ n ≤ 1 000, n ≤ k ≤ 2 000, 1 ≤ p ≤ 109) — the number of people, the number of keys and the office location.

The second line contains n distinct integers a1, a2, ..., an (1 ≤ ai ≤ 109) — positions in which people are located initially. The positions are given in arbitrary order.

The third line contains k distinct integers b1, b2, ..., bk (1 ≤ bj ≤ 109) — positions of the keys. The positions are given in arbitrary order.

Note that there can't be more than one person or more than one key in the same point. A person and a key can be located in the same point.

Output

Print the minimum time (in seconds) needed for all n to reach the office with keys.

Examples
input
2 4 50
20 100
60 10 40 80
output
50
input
1 2 10
11
15 7
output
7

Note

In the first example the person located at point 20 should take the key located at point 40 and go with it to the office located at point 50. He spends 30 seconds. The person located at point 100 can take the key located at point 80 and go to the office with it. He spends 50seconds. Thus, after 50 seconds everybody is in office with keys.


题目大意:n个人,k把钥匙,人取钥匙后到达目的地,问n个人全部到达后所需的最短时间
思路:二分,贪心
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 2005
typedef long long ll;
using namespace std;

int n, k, p;
int a[maxn], b[maxn];
bool check(ll x)
{
	int pos = -1;
	for (int i = 0; i < n; i++) {
		while (pos < k) {
			pos++;
			if ((abs(a[i] - b[pos]) + abs(b[pos] - p)) <= x) break;
		}
		if (pos >= k) return false;
	}
	return true;
}
int main()
{
	while (~scanf("%d%d%d", &n, &k, &p)) {
		for (int i = 0; i < n; i++)
			scanf("%d", &a[i]);
		for (int i = 0; i < k; i++)
			scanf("%d", &b[i]);
		sort(a, a + n);
		sort(b, b + k);
		ll l = 0, r = 2e9, ans;
		while (l <= r) {
			ll mid = (r + l) / 2;
			if (check(mid)) {
				ans = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		printf("%I64d\n", ans);
	}
	return 0;
}

2017-07-14 18:13:55 mengxiang000000 阅读数 1074
  • redis高并发处理由浅入深(备java基础,javaee课程)

    Redis是一款依据BSD开源协议发行的高性能Key-Value存储系统(cache and store)。 命令主要分以下几部分关键字(Keys) 字符串(String) 哈希(Hashs) 列表(Lists) 集合(Sets) 有序集合(Sorted Sets)HyperLogLog 发布/订阅(Pub/Sub) 事务(Transactions) 脚本(Scripting)

    11828 人正在学习 去看看 任亮

D. Office Keys
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are n people and k keys on a straight line. Every person wants to get to the office which is located on the line as well. To do that, he needs to reach some point with a key, take the key and then go to the office. Once a key is taken by somebody, it couldn't be taken by anybody else.

You are to determine the minimum time needed for all n people to get to the office with keys. Assume that people move a unit distance per1 second. If two people reach a key at the same time, only one of them can take the key. A person can pass through a point with a key without taking it.

Input

The first line contains three integers n,k andp (1 ≤ n ≤ 1 000,n ≤ k ≤ 2 000,1 ≤ p ≤ 109) — the number of people, the number of keys and the office location.

The second line contains n distinct integersa1, a2, ..., an (1 ≤ ai ≤ 109) — positions in which people are located initially. The positions are given in arbitrary order.

The third line contains k distinct integersb1, b2, ..., bk (1 ≤ bj ≤ 109) — positions of the keys. The positions are given in arbitrary order.

Note that there can't be more than one person or more than one key in the same point. A person and a key can be located in the same point.

Output

Print the minimum time (in seconds) needed for all n to reach the office with keys.

Examples
Input
2 4 50
20 100
60 10 40 80
Output
50
Input
1 2 10
11
15 7
Output
7
Note

In the first example the person located at point 20 should take the key located at point40 and go with it to the office located at point50. He spends 30 seconds. The person located at point100 can take the key located at point80 and go to the office with it. He spends 50 seconds. Thus, after50 seconds everybody is in office with keys.


题目大意:


给你N个人,有K把钥匙,终点为P.


每个人要求拿一把钥匙到终点,问多长时间,能够使得所有人都做到。


思路:


设定Dp【i】【j】表示前i个人,在前j把钥匙中都拿到了钥匙,并且到终点的最优最长需求时间。


那么有:


if(i==j)Dp【i】【j】=max(Dp【i-1】【j-1】,第i个人走到钥匙j并且到终点的花费);

else Dp【i】【j】=min(Dp【i】【j-1】,max(Dp【i-1】【j-1】,第i个人走到钥匙j并且到终点的花费));


Ac代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<climits>
using namespace std;
int a[150000];
int b[150000];
int dp[1005][1005];
int main()
{
    int n,k,p;
    while(~scanf("%d%d%d",&n,&k,&p))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        for(int i=1;i<=k;i++)scanf("%d",&b[i]);
        sort(a+1,a+1+n);
        sort(b+1,b+1+k);
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=k;j++)
            {
                if(i==j)
                {
                    dp[i][j]=max(dp[i-1][j-1],abs(p-b[j])+abs(a[i]-b[j]));
                    continue;
                }
                dp[i][j]=min(dp[i][j-1],max(dp[i-1][j-1],abs(p-b[j])+abs(a[i]-b[j])));
            }
        }
        int output=INT_MAX;
        for(int i=n;i<=k;i++)
        {
            output=min(output,dp[n][i]);
        }
        printf("%d\n",output);
    }
}

二分思路:


二分时间,贪心check.

每个人,尽量拿左边的钥匙即可。

Ac代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<climits>
using namespace std;
#define ll __int64
ll a[150000];
ll b[150000];
ll n,k,p;
ll Slove(ll mid)
{
    ll output=0;
    ll now=1;
    for(ll i=1;i<=n;i++)
    {
        while(now<=k&&abs(b[now]-a[i])+abs(b[now]-p)>mid)
        {
            now++;
        }
        if(now<=k)
        {
            now++;
            output++;
        }
        else break;
    }
    if(output>=n)return 1;
    else return 0;
}
int main()
{
    while(~scanf("%I64d%I64d%I64d",&n,&k,&p))
    {
        for(ll i=1;i<=n;i++)scanf("%I64d",&a[i]);
        for(ll i=1;i<=k;i++)scanf("%I64d",&b[i]);
        sort(a+1,a+1+n);
        sort(b+1,b+1+k);
        ll ans=-1;
        ll l=0;
        ll r=2000000000+50;
        while(r>=l)
        {
            ll mid=(l+r)/2;
            if(Slove(mid)==1)
            {
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        printf("%I64d\n",ans);
    }
}












没有更多推荐了,返回首页