算法设计与分析复习题 pta（第3章 分治法）

7-1 魔法优惠券

#include<iostream>
#include <stdio.h>
#include <string.h>
int cmp(const void *a,const void *b) {
    return *(int *)b-*(int *)a;
}
int main() {
    int n;
    scanf("%d",&n);
    int i,j;
    int a[n];
    memset(a,0,sizeof(a));
    for(i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    qsort(a,n,sizeof(int),cmp);
    int m;
    scanf("%d",&m);
    int b[m];
    memset(b,0,sizeof(b));
    for(i=0; i<m; i++) {
        scanf("%d",&b[i]);
    }
    qsort(b,m,sizeof(int),cmp);
    int sum=0;
    int p1=0,q1=n-1;
    int p2=0,q2=m-1;
    while(p1<=q1&&p2<=q2) {//从前往后
        if(a[p1]*b[p2]>0) {
            sum+=a[p1]*b[p2];
            p1++;
            p2++;
        } else
            break;
    }
    while(p1<=q1&&p2<=q2) {//从后往前
        if(a[q1]*b[q2]>0) {
            sum+=a[q1]*b[q2];
            q1--;
            q2--;
        } else
            break;
    }
    printf("%d",sum);
    return 0;
}

7-2 插入排序还是归并排序

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<bits/stdc++.h>
using namespace std;
void PrintResult(int *P, int N)
{
    for(int i=0; i<N; i++)
    {
        if(i==0)
            printf("%d", P[i]);
        if(i!=0)
            printf(" %d", P[i]);
    }
}
int IsInsertion(int *P, int *PMid, int N)
{
    int i;
    for(i=0; i<N-1; i++)
    {
        if(PMid[i]>PMid[i+1])
            break;
    }
    for(int j=i+1; j<N; j++)
    {
        if(P[j]!=PMid[j])
            return 0;
    }
  //finishing the sort is impossible, beacause the InsertionSort is the same as MergeSort in this situation
        return i;
}
void NextInsertion(int *PMid, int k, int N)
{
    printf("Insertion Sort\n");
    int i;
    int tmp = PMid[k+1];
    for(i=k+1; i>0 && PMid[i-1]>tmp ; i--)
        PMid[i] = PMid[i-1];
    PMid[i] = tmp;
    PrintResult(PMid, N);
}
int MergeLength(int *PMid, int N)
{
    int L,i;
    for(L=2; L<N; L=2*L)
    {
        for(i=1; L*i<N; i+=2)
        {
            if(PMid[L*i-1]>PMid[L*i])
                return L;
        }
    }
}
void Merge(int *A, int *tmpA, int L, int R, int RightEnd)
{
    int LeftEnd = R-1;
    int tmpi = L;
    while(L<=LeftEnd && R<=RightEnd)
    {
        if(A[L]>A[R])
            tmpA[tmpi++] = A[R++];
        else
            tmpA[tmpi++] = A[L++];
    }
    for(; L<=LeftEnd; )    tmpA[tmpi++] = A[L++];
    for(; R<=RightEnd; )   tmpA[tmpi++] = A[R++];
}
void NextMerge(int *PMid, int N)
{
    printf("Merge Sort\n");
    int *tmpA = (int *)malloc(N*sizeof(int));
    int L = MergeLength(PMid, N);
    int i,j;
    for(i=0; (i+1)*2*L-1<N ;i++)
        Merge(PMid, tmpA, i*2*L, i*2*L+L, (i+1)*2*L-1);

    if(i*2*L+L-1<N)     //one part is complete, and the other part is incomplete
    {
        Merge(PMid, tmpA, i*2*L, i*2*L+L, N-1);
    }
    if(i*2*L+L-1>=N)     //surplus part is incomplete
    {
        for(j=i*2*L; j<N; j++)
            tmpA[j] = PMid[j];
    }

7-3 德才论

#include<bits/stdc++.h>
using namespace std;
int n ,m, k, l,h;
struct node {
    string kaohao;
    int de, cai, dengji, sum;
}a[101001];
int cmp(node x, node y){
    if(x.dengji != y.dengji)
        return x.dengji < y.dengji;
    if(x.sum != y.sum)
        return x.sum > y.sum;
    else if(x.de != y.de )
        return x.de > y.de;
    return x.kaohao < y.kaohao;
}
int main()
{
    cin >> n >> l >> h;

    for(int i = 0; i < n ; i ++){
        cin >> a[i].kaohao >> a[i].de >> a[i].cai;
        a[i].sum = a[i].de + a[i].cai;
        
        if(a[i].de >= h && a[i].cai >= h) a[i].dengji = 1;
        else if(a[i].de >= h && a[i].cai >= l) a[i].dengji = 2;
        else if(a[i].de >= l && a[i].cai >= l && a[i].de >= a[i].cai) a[i].dengji = 3;
        else if(a[i].de >= l && a[i].cai >= l) a[i].dengji = 4;
        else a[i].dengji = 5;
        if(a[i].dengji < 5) k ++;
    }
    sort(a, a + n, cmp);
    cout << k << endl;
    for(int i = 0; i < k; i ++)
    {
        cout << a[i].kaohao << ' ' << a[i].de << ' ' << a[i].cai << endl;
    }
}

7-4 全排列（分治）

#include<iostream>
#include<stdio.h>
using namespace std;
void     pailie    (int a[],int k,int m)    {
    if(k==m){
            for(int i=0;i<=m;i++){
                    printf("%d ",a[i]);
            }
        printf("\n");
    }
    for(int j=k;j<=m;j++){
    swap(a[j],a[k]);
        pailie(a,k+1,m);
        swap(a[j],a[k]);
    }
}
int main(){
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i;i<n;i++){
        a[i]=i+1;
    }
    pailie(a,0,n-1);
    return 0;
}

7-5 h0030. 数组的和（10分得4分）

#include <iostream>
#include <vector>
using namespace std;
long long count_subarray_sums(int N, long long T, vector<int>& array) {
    long long count = 0;
    vector<long long> prefix_sum(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        prefix_sum[i] = prefix_sum[i - 1] + array[i - 1];
    }
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            if (prefix_sum[j] - prefix_sum[i] < T) {
                count++;
            }
        }
    }
    return count;
}
int main() {
    int N;
    long long T;
    cin >> N >> T;
    vector<int> array(N);

    for (int i = 0; i < N; ++i) {
        cin >> array[i];
    }
    long long result = count_subarray_sums(N, T, array);
    cout << result << endl;
    return 0;
}

7-6 h0194. 棋盘分割

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
const int M = 16;
int g[N][N];
double f[N][N][N][N][M];
int s[N][N];
int n,m = 8;
double X;
const int INF = 0x3f3f3f3f;
double get(int x1,int y1,int x2,int y2){ 
   
     double sum = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1] - X;
     return sum * sum / n;
}
double dp(int x1,int y1,int x2,int y2,int k){ 
   
    double &v = f[x1][y1][x2][y2][k];
    if(v >= 0)return v;
    if(k == 1)return get(x1,y1,x2,y2);
    v = INF;
    for(int i = x1;i < x2;i ++){ 
   
        v = min(v,dp(x1,y1,i,y2,k - 1) + get(i + 1,y1,x2,y2));
        v = min(v,get(x1,y1,i,y2) + dp(i + 1,y1,x2,y2,k - 1));
    }
    for(int i = y1;i < y2;i ++){ 
   
        v = min(v,dp(x1,y1,x2,i,k - 1) + get(x1,i + 1,x2,y2));
        v = min(v,get(x1,y1,x2,i) + dp(x1,i + 1,x2,y2,k - 1));
    }
    return v;
}
int main(){ 
    cin>>n;
    memset(f,-1,sizeof f);
    for(int i = 1;i <= m;i ++){ 
   
        for(int j = 1;j <= m;j ++){ 
   
            cin>>g[i][j];
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + g[i][j];
        }
    }
    X = (double)s[m][m] / n;
    double res = dp(1,1,m,m,n);
    printf("%.3f",sqrt(res));
    return 0;
}

7-7 h0198. 放弃考试

#include <iostream>
#include <cstdio>
#include <algorithm>
const int N = 1005;
using namespace std;
int n,k;
double a[N],b[N],c[N];
bool check(double t){
    for(int i = 0;i < n;i++)    c[i] = a[i] - t * b[i];
    sort(c,c + n);
    double s = 0;
    for(int i = n - 1;i >= k;i--) s += c[i];
    if(s >= 0)  return true;
    return false;
}
int main(){
    while(cin>>n>>k,n){
        for(int i = 0;i < n;i++)    cin>>a[i];
        for(int i = 0;i < n;i++)    cin>>b[i];
        double l = 0,r = 1e9;
        while(r - l > 1e-6){
            double mid = (l + r) / 2;
            if(check(mid))  l = mid;
            else    r = mid;
        }
        int res = 100 * l + 0.5;
        printf("%d\n",res);
    }
    return 0;
}

7-8 h0201. 矩形分割

#include<iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define p 10001
using namespace std;
struct node{
    int l;
    int t;
    int w;
    int h;
}nodes[p];
int r,n;
long long cha;
int mid,lleft,rright;
long long check(int mid){//返回左右小矩形面积之差
    long long larea=0;
    long long rarea=0;
    for(int i=0;i<n;i++){
        if(nodes[i].l>=mid){
            rarea+=nodes[i].w*nodes[i].h;
        }
        else{
            if(nodes[i].l+nodes[i].w>mid){    //分割线位于矩形中间时
                rarea+=(nodes[i].l+nodes[i].w-mid)*nodes[i].h;
                larea+=(mid-nodes[i].l)*nodes[i].h;
            }
            else{
                larea+=nodes[i].w*nodes[i].h;
            }
        }
    }
    cha=larea-rarea;
    return cha;
}
int zhixian(){
    lleft=0;
    rright=r;
     while(lleft<=rright)
        {
        mid=(lleft+rright)/2;
        if(check(mid)<0)
            lleft=mid+1;
        else if(check(mid)>0)//此时左边小矩形总面积大于右边的了，为使左右面积之差最小，分割线再往右移
           rright=mid-1;
        else
            return mid;
    }
 
    return lleft;
}
int main(){
    scanf("%d",&r);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d%d%d",&nodes[i].l,&nodes[i].t,&nodes[i].w,&nodes[i].h);
    }
    if(n==1&&nodes[n-1].w==1){//当只有一个矩形且宽为1时，因不能在其中间进行分割，故分割线直接为大矩形的右端坐标
        printf("%d\n",r);
        return 0;
    }
    int aa=zhixian();
    while(check(aa)==check(aa+1)&&aa<r)//此时已找到使两边面积之差最小的分割线，为了使左侧大矩形面积最大，若分割线往右移，恰好处于空白区域，即左右两边小矩形面积之差不变
        aa++;
     printf("%d\n",aa);
 
}

7-9 h0315. 笨拙的手指

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>

using namespace std;
string a,b;

//将b 进制的数字转换为 十进制
int get(string s,int b)
{
    //使用秦九韶算法实现
    //类似于提取公因式的计算方法，与 计算机基础中 手动计算的方法基本一致
    int res=0;
    for(auto c:s)
    {
        res=res*b+c-'0';
    }
    return res;
    
}
int main()
{
    //读入这两个数字
    cin>>a>>b;
    
    //定义一个哈希表，因为最后要通过比较这两个 集合 来判断这个唯一解
    unordered_set<int> s;
    
    //二进制中寻找每一位不同的结果
    for(auto& c:a)  //这里的是引用 因为每次都要保证 a 只能被修改一位
    {
        //a为二进制，每一位要么是0，要么是1，要实验每一位 写错之后的值
        c^=1;   //将0变1，将1变0
        s.insert(get(a,2));     //get 函数的作用就是 将 任意进制的数字转换为十进制，将这个十进制数字放入 哈希表中
        c^=1;   //将这一位 复原，继续修改下一位
    }
    
    //三进制中 寻找每一位的结果
    for(auto& c:b)
    {
        char t=c;
        //三进制中对于每一种可能的选择，这里直接遍历，只要这一位变成和先前不同即可 与二进制转换的十进制进行比较
        for(int i=0;i<3;i++)
        {
            //如果该位写错
            if(i+'0'!=t)
            {
                //转换为数字
                c=i+'0';
                int x=get(b,3);
                //如果在 哈希表中 存在该转换好的十进制数字，且答案唯一 ，就可以得到结果了
                if(s.count(x))
                {
                    cout<<x<<"\n";
                    return 0;
                }
            }
        }
        //如果该位没有写错，就需要将该位 恢复原状，然后比较下一位
        c=t;
        
    }
    
    return 0;
}