程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #277.5 (Div. 2)

Codeforces Round #277.5 (Div. 2)

編輯：C++入門知識

Codeforces Round #277.5 (Div. 2)

題目1：

題意：問最少的交換次數，使序列不遞減。且交換次數不超過n。

思路：既然不超過n，那麼就使用選擇排序，盡管復雜度很高，但是交換次數確是至少的。每次找出最小值，然後和當前值交換即可。

題目：

A. SwapSort time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

In this problem your goal is to sort an array consisting of n integers in at most n swaps. For the given array find the sequence of swaps that makes the array sorted in the non-descending order. Swaps are performed consecutively, one after another.

Note that in this problem you do not have to minimize the number of swaps — your task is to find any sequence that is no longer than n.

Input

The first line of the input contains integer n (1?≤?n?≤?3000) — the number of array elements. The second line contains elements of array: a0,?a1,?...,?an?-?1 (?-?109?≤?ai?≤?109), where ai is the i-th element of the array. The elements are numerated from 0 to n?-?1 from left to right. Some integers may appear in the array more than once.

Output

In the first line print k (0?≤?k?≤?n) — the number of swaps. Next k lines must contain the descriptions of the k swaps, one per line. Each swap should be printed as a pair of integers i, j (0?≤?i,?j?≤?n?-?1), representing the swap of elements ai and aj. You can print indices in the pairs in any order. The swaps are performed in the order they appear in the output, from the first to the last. It is allowed to print i?=?jand swap the same pair of elements multiple times.

If there are multiple answers, print any of them. It is guaranteed that at least one answer exists.

Sample test(s) input

5
5 2 5 1 4

output

2
0 3
4 2

input

6
10 20 20 40 60 60

output

input

2
101 100

output

1
0 1

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
priority_queue,greater >Q;

const int maxn=3000+10;

int n,a[maxn];
struct Node
{
    int x,y;
}node[maxn];

int main()
{
    int cnt=0;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            int p=i;
            for(int j=i+1;j<=n;j++)
            {
                if(a[j]

題目b
題意：告訴n個男孩，和m個女孩，然後分別告訴他們跳舞的水平，然後男女能夠匹配的條件是他們的水平最多相差1,。
思路：直接對他們的水平進行排列，那麼就可以愉快的貪心了，然後找出每個男孩能夠匹配的水平，然後從小到大選擇，越小越好，因為如果選的稍微大的，可能會影響後面的水平高的男孩的舞伴，所以從小到大貪是正確的。
題目：


B. BerSU Ball


time limit per test
1 second


memory limit per test
256 megabytes


input
standard input


output
standard output



The Berland State University is hosting a ballroom dance in celebration of its 100500-th anniversary! n boys and m girls
 are already busy rehearsing waltz, minuet, polonaise and quadrille moves.

We know that several boy&girl pairs are going to be invited to the ball. However, the partners' dancing skill in each pair must differ by at most one.

For each boy, we know his dancing skills. Similarly, for each girl we know her dancing skills. Write a code that can determine the largest possible number of pairs that can be formed from n boys
 and m girls.



Input

The first line contains an integer n (1?≤?n?≤?100)
 — the number of boys. The second line contains sequence a1,?a2,?...,?an (1?≤?ai?≤?100),
 where ai is
 the i-th boy's dancing skill.

Similarly, the third line contains an integer m (1?≤?m?≤?100)
 — the number of girls. The fourth line contains sequence b1,?b2,?...,?bm (1?≤?bj?≤?100),
 where bj is
 the j-th girl's dancing skill.



Output

Print a single number — the required maximum possible number of pairs.



Sample test(s)



input
4
1 4 6 2
5
5 1 5 7 9




output
3




input
4
1 2 3 4
4
10 11 12 13




output
0




input
5
1 1 1 1 1
3
1 2 3




output
2



代碼：

#include
#include
#include
#include
using namespace std;

const int maxn=100+10;

int a[maxn],b[maxn],n,m;

bool vis[maxn];

int main()
{
    int ans,l,mid,r;
    while(~scanf("%d",&n))
    {
        ans=0;
        memset(vis,false,sizeof(vis));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
            scanf("%d",&b[i]);
        sort(a+1,a+1+n);
        sort(b+1,b+1+m);
        for(int i=1;i<=n;i++)
        {
            l=a[i]-1,mid=a[i],r=a[i]+1;
            for(int j=1;j<=m;j++)
            {
                if(!vis[j])
                {
                    if(b[j]==l)
                    {
                        ans++;
                        vis[j]=true;
                        break;
                    }
                    else if(b[j]==mid)
                    {
                        ans++;
                        vis[j]=true;
                        break;
                    }
                    else if(b[j]==r)
                    {
                        ans++;
                        vis[j]=true;
                        break;
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}


題目3：
題目，給出m，s，意思就是確定兩個數，他們都有m位，然後每位的和加起來都是s。
思路：構造，最大值比較好求，就是從最高位向最低位選擇，然後最後不滿9的，下一位就是這個數，然後直接跳出來後面的全是0，在構造最小的值，最小的值首先最高位直接賦值為1，然後從最低位每位按9算，最後不足9的直接把最後的值賦給這一位，如果直到最高位還有值，那麼最高位==ss+1，最小值也構造完成。。
ps：還要注意幾個問題，首先是直接輸出-1 -1的，就是s==0或者9*m
題目：


C. Given Length and Sum of Digits...


time limit per test
1 second


memory limit per test
256 megabytes


input
standard input


output
standard output



You have a positive integer m and a non-negative integer s.
 Your task is to find the smallest and the largest of the numbers that have length m and sum of digits s.
 The required numbers should be non-negative integers written in the decimal base without leading zeroes.



Input

The single line of the input contains a pair of integers m, s (1?≤?m?≤?100,?0?≤?s?≤?900)
 — the length and the sum of the digits of the required numbers.



Output

In the output print the pair of the required non-negative integer numbers — first the minimum possible number, then — the maximum possible number. If no numbers satisfying conditions required exist, print the pair of numbers "-1
 -1" (without the quotes).



Sample test(s)



input
2 15




output
69 96




input
3 0




output
-1 -1



代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-9
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
priority_queue,greater >Q;

const int maxn=100+10;

int m,xx;
char s[maxn],t[maxn];


int main()
{
    int ss;
    while(~scanf("%d%d",&m,&xx))
    {
       for(int i=0;i9*m||(xx==0&&m>1))
       {
           puts("-1 -1");
           continue;
       }
       else
       {
           ss=xx;
           ss--;
           t[0]='1';
           for(int i=m-1;i>0;i--)
           {
               int x=min(ss,9);
               if(x==0)  break;
               t[i]=x+'0';
               ss-=x;
           }
           if(ss)  t[0]=ss+1+'0';
           for(int i=0;i0)
               {
                   s[i]=9+'0';
                   ss=ss-9;
               }
               else
               {
                   s[i]=ss+'0';
                   break;
               }
           }
           for(int i=0;i