CF 0798D 二维贪心 随机算法 随机洗牌

一. 贪心算法
C++

#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1e3+5;
const int maxx=1e5+100;
struct node
{
    int x,y,id;
}Q[maxx];

bool cmp(node a,node b)
{
    return a.x>b.x;
}
int main(int argc, char* argv[])
{
    int n;
    freopen("0798Di.txt","r",stdin);
    cin>>n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> Q[i].x;
        Q[i].id = i;
    }
    for(int i = 1 ; i <= n ; i++)
        cin >> Q[i].y;
    sort(Q+1,Q+n+1,cmp);
    cout << n / 2 + 1 << endl;
    cout <<Q[1].id;
    if(n % 2 == 0)
    {
        for(int i=2;i<n-1;i+=2)
        {
            if(Q[i].y<Q[i+1].y)
                printf(" %d",Q[i+1].id);
            else printf(" %d",Q[i].id);
        }
        printf(" %d",Q[n].id);
    }
    else
    {
        for(int i=2;i<n;i+=2)
        {
            if(Q[i].y<Q[i+1].y)
                printf(" %d",Q[i+1].id);
            else printf(" %d",Q[i].id);
        }
    }
    return 0;
}
/*
5
8 7 4 8 3
4 2 5 3 7
3
1 4 5
*/

C code begin

#include <stdio.h>

const int maxn=1e3+5;
const int maxx=1e5+100;
typedef struct node
{
   int x,y,id;
}Tque;

Tque Q[maxx];

void quick_sort(Tque Q[], int l, int r)
{
   int i,j;
   Tque val;
   if(l<r){
      i=l;
      j=r;
      val.x=Q[l].x;
      val.y=Q[l].y;
      val.id=Q[l].id;
      while(i<j){
         while(i<j && Q[j].x <= val.x)
            j--;
         if(i<j){
            Q[i].x=Q[j].x;
            Q[i].y=Q[j].y;
            Q[i].id=Q[j].id;
            i+=1;
         }
         while(i<j && Q[i].x > val.x)
            i++;
         if(i<j){
            Q[j].x=Q[i].x;
            Q[j].y=Q[i].y;
            Q[j].id=Q[i].id;
            j-=1;
         }
      }

      Q[i].x=val.x;
      Q[i].y=val.y;
      Q[i].id=val.id;
      quick_sort(Q,l,i-1);
      quick_sort(Q,i+1,r);
   }
}

int main(int argc, char* argv[])
{
   int n;
   int i;
   freopen("0798Di.txt","r",stdin);
   scanf("%d", &n);
   for(i=1;i<=n;i++)
   {
      scanf("%d", &Q[i].x);
      Q[i].id = i;
   }
   for(i=1;i<=n;i++)
      scanf("%d", &Q[i].y);

   quick_sort(Q,1,n);
   printf("%d\n%d", n/2+1, Q[1].id);
   if(n%2 == 0)
   {
      for(i=2;i<n-1;i+=2)
      {
         if(Q[i].y<Q[i+1].y)//每次取出两个,比较y值,取y值大的
            printf(" %d",Q[i+1].id);
         else printf(" %d",Q[i].id);
      }
      printf(" %d",Q[n].id);
   }
   else
   {
      for(i=2;i<n;i+=2)
      {
         if(Q[i].y<Q[i+1].y)//每次取出两个,比较y值,取y值大的
            printf(" %d",Q[i+1].id);
         else printf(" %d",Q[i].id);
      }
   }
   return 0;
}
/*
in:
5
8 7 4 8 3
4 2 5 3 7
out:
3
1 4 5
*/

C code end

二. 随机算法

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

const int maxn=1e3+5;
const int maxx=1e5+100;

int a[maxx],b[maxx],c[maxx];

void swap(int &a, int &b)
{
   int t; t=b; b=a; a=t;
}

void random_shuffle(int array[], int len)
{
   int i;
   int j;
   for(i=1;i<len;i++){
      j=rand()%(i+1);
      swap(array[i],array[j]);
   }
}

int main(int argc, char* argv[])
{
   int i,n,p;
   long long sum1=0,sum2=0,fa=0,fb=0;
   freopen("0798Di.txt","r",stdin);
   scanf("%d", &n);
   p=n/2+1;

   for(i=1;i<=n;i++){
      scanf("%d", &a[i]);
      c[i]=i;
      sum1+=a[i];
   }
   for(i=1;i<=n;i++){
      scanf("%d", &b[i]);
      sum2+=b[i];
   }
   printf("%d\n",p);
   while(1){
      random_shuffle(c+1,n);
      for(i=1;i<=p;i++){
         fa+=a[c[i]];
         fb+=b[c[i]];
      }
      if(2*fa>sum1 && 2*fb>sum2){
         for(i=1;i<=p;i++)
            printf("%d ",c[i]);
         printf("%\n");
         break;
      }
   }
   return 0;
}

三. 随机洗牌
将一个数组中的元素序列打算顺序进行重排，并需要保证重排后的每一种结果是等概率且随
机的。下面的两种算法哪一种是正确的？（注：random(a,b)返回一个a~b的随机整数）
1. for i=1 to n do swap( a[i], a[random(1,n)] );
2. for i=1 to n do swap( a[i], a[random(i,n)] );

解释：
首先，1～n的序列打乱重排共有n!个不同的排列，且每种排列被选中的概率为1/N!，只有这
样的算法才是等概率且随机的。

第一种算法将会产生n^n种情况，显然其中出现了重复的情况。那么会不会虽然出现重复，
但每种排列重复的次数相同，所以算法依然是等概率且随机的呢？答案是，不会。

假设上述情况成立，则n^n必定n!整除。但是，绝大多数情况下，n!的质因子远多于n^n的质
因子（即n的质因子。根据Bertrand-Chebyshev定理，在n/2和n之间一定还有一个质数。这
两个质数的乘积已经大于n了。搞了半天，第一种看似对称而美观的算法居然是错的！即对
所有大于2的n，上述整除都不不可能的。

第二种算法是符合要求的随机洗牌算法。

使用数学归纳法证明：

1、当n=1时，所以元素arr[0]在任何一个位置的概率为1/1，命题成立。
2、假设当n=k时，命题成立，即原数组中任何一个元素在任何一个位置的概率为1/k。

3、则当n=k+1时，当算法执行完k次时，前k个元素在前k个位置的概率均为1/k。当执行最后
   一步时，前k个元素中任何一个元素被替换到第k+1位置的概率为：
      (1-1/(k+1)) * 1/k = 1/(k+1);
   在前面k个位置任何一个位置的概率为
       (1-1/(k+1)) * 1/k = 1/(k+1);
    故前k个元素在任意位置的的概率都为1/(k+1)所以，对于前k个元素，
    它们在k+1的位置上概率为1/(k+1)。对于第k+1个元素，其在原位置的概率为1/k+1，在
    前k个位置任何一个位置的概率为：(1-k/（k+1)） * (1/k)=1/（k+1），
   所以对于第k+1个元素，其在整个数组前k+1个位置上的概率也均为1/k+1。

综上所述，对于任意n，只要按照方案中的方法，即可满足每个元素在任何一个位置出现的
概率均为1/n。