过河

C 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2022-06-20

#include <stdio.h>

void quickSort(int *nums, int start, int end) {
    if (start < end) {
        int rIndex = rand() % (end - start + 1) + start, tmp;
        tmp = nums[rIndex];
        nums[rIndex] = nums[start];
        nums[start] = tmp;
        
        int target = nums[start], i = start, j = end;
        while(i < j) {
            while(i < j && nums[j] > target) {
                j--;
            }
            if(i < j) {
                nums[i++] = nums[j];
            }
            while(i < j && nums[i] <= target) {
                i++;
            }
            if(i < j) {
                nums[j--] = nums[i];
            }
        }
        nums[i] = target;
        
        quickSort(nums, start, i - 1);
        quickSort(nums, i + 1, end);
    }
}

int min(int a, int b) {
    return a > b ? b : a;
}

int main() {
    int L;
    scanf("%d", &L);
    
    int s, t, m;
    scanf("%d %d %d", &s, &t, &m);
    
    int *nums = (int *)malloc(sizeof(int) * m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &nums[i]);
    }
    
    quickSort(nums, 0, m - 1);
    
    if (s == t) {
        int count = 0;
        for (int i = 0; i < m; i++) {
            if (nums[i] % s == 0) {
                count++;
            }
        }
        printf("%d", count);
    } else {
        int lastNIndex = 0;

        int *dp = (int *)malloc(sizeof(int) * 10000); //(2 * t + 1)
        int j = 0, minDP, len = 10000;
        dp[0] = 0;

        int k = s * t, d = 0, x;
        if (nums[0] > k) {
            d = nums[0] - k;
            nums[0] -= d;
        }
        for (int i = 1; i < m; i++) {
            x = nums[i] - d - nums[i - 1];
            if (x > k) {
                d += (x - k);
            }
            nums[i] -= d; 
        }

        x = L - d - nums[m - 1];
        if (x > k) {
            d += (x - k);
        }
        L -= d;

        for (int i = 1; i < s; i++) {
            if (lastNIndex != m && nums[lastNIndex] == i) {
                lastNIndex++;
            }
            dp[i] = 101;
        }
        for (int i = s; i <= t; i++) {
            if (lastNIndex != m && nums[lastNIndex] == i) {
                lastNIndex++;
                dp[i] = 1;
            } else {
                dp[i] = 0;
            }
        }

        for (int i = t + 1; i <= (L + t - 1); i++) {
            minDP = 101;
            for (j = t; j >= s; j--) {
                minDP = min(minDP, dp[(i-j)%len]);
            }
            if (lastNIndex != m && nums[lastNIndex] == i) {
                lastNIndex++;
                dp[i%len] = minDP + 1;
            } else {
                dp[i%len] = minDP;
            }
        }

        minDP = 101;
        for (int i = L; i <= (L + t - 1); i++) {
            minDP = min(minDP, dp[i%len]);
        }

        printf("%d", minDP);
        
        free(dp);
    }
    
    
    free(nums);
    
    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 336KB, 提交时间: 2022-07-12

#include <stdio.h>

void quickSort(int *nums, int start, int end) {
    if (start < end) {
        int rIndex = rand() % (end - start + 1) + start, tmp;
        tmp = nums[rIndex];
        nums[rIndex] = nums[start];
        nums[start] = tmp;
        
        int target = nums[start], i = start, j = end;
        while(i < j) {
            while(i < j && nums[j] > target) {
                j--;
            }
            if(i < j) {
                nums[i++] = nums[j];
            }
            while(i < j && nums[i] <= target) {
                i++;
            }
            if(i < j) {
                nums[j--] = nums[i];
            }
        }
        nums[i] = target;
        
        quickSort(nums, start, i - 1);
        quickSort(nums, i + 1, end);
    }
}

int min(int a, int b) {
    return a > b ? b : a;
}

int main() {
    int L;
    scanf("%d", &L);
    
    int s, t, m;
    scanf("%d %d %d", &s, &t, &m);
    
    int *nums = (int *)malloc(sizeof(int) * m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &nums[i]);
    }
    
    quickSort(nums, 0, m - 1);
    
    if (s == t) {
        int count = 0;
        for (int i = 0; i < m; i++) {
            if (nums[i] % s == 0) {
                count++;
            }
        }
        printf("%d", count);
    } else {
        int lastNIndex = 0;

        int *dp = (int *)malloc(sizeof(int) * 10000); //(2 * t + 1)
        int j = 0, minDP, len = 10000;
        dp[0] = 0;

        int k = s * t, d = 0, x;
        if (nums[0] > k) {
            d = nums[0] - k;
            nums[0] -= d;
        }
        for (int i = 1; i < m; i++) {
            x = nums[i] - d - nums[i - 1];
            if (x > k) {
                d += (x - k);
            }
            nums[i] -= d; 
        }

        x = L - d - nums[m - 1];
        if (x > k) {
            d += (x - k);
        }
        L -= d;

        for (int i = 1; i < s; i++) {
            if (lastNIndex != m && nums[lastNIndex] == i) {
                lastNIndex++;
            }
            dp[i] = 101;
        }
        for (int i = s; i <= t; i++) {
            if (lastNIndex != m && nums[lastNIndex] == i) {
                lastNIndex++;
                dp[i] = 1;
            } else {
                dp[i] = 0;
            }
        }

        for (int i = t + 1; i <= (L + t - 1); i++) {
            minDP = 101;
            for (j = t; j >= s; j--) {
                minDP = min(minDP, dp[(i-j)%len]);
            }
            if (lastNIndex != m && nums[lastNIndex] == i) {
                lastNIndex++;
                dp[i%len] = minDP + 1;
            } else {
                dp[i%len] = minDP;
            }
        }

        minDP = 101;
        for (int i = L; i <= (L + t - 1); i++) {
            minDP = min(minDP, dp[i%len]);
        }

        printf("%d", minDP);
        
        free(dp);
    }
    
    
    free(nums);
    
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 400KB, 提交时间: 2022-05-19

#include<iostream>
#include<algorithm>
using namespace std;
int L, s, t, m, ans;
int a[110];  //石子的位置
int f[11000] = {0}; //f[x]表示青蛙跳到位置i最少踏的石子数
int stone[11000] = {0}; //stone[x]表示位置x是否是石子，0表示不是，1表示是
void solve() {
    int d = 0, k = s * t, x; //d表示累加平移量，k表示s和t的公倍数
    for (int i = 1; i <= m + 1; i++) {
        x = a[i] - d - a[i - 1]; //x表示第i个石子和第i-1个石子的距离
        if (x > k) d += x - k; //超过公倍数部分用作平移
        a[i] = a[i] - d;
        stone[a[i]] = 1; //标记平移后位置是石子
    }
    stone[a[m + 1]] = 0; //桥尾不是石子
    f[0] = 0;
    for (int i = 1; i <= a[m + 1] + t - 1;
            i++) { //考查桥上到桥尾的所有位置
        f[i] = 105;
        for (int j = s; j <= t;
                j++) //在i的前一个位置中找一个经历石子最少的
            if (i >= j) f[i] = min(f[i], f[i - j]);
        f[i] += stone[i]; //加上当前位置石子数
    }
    ans = 101;
    for (int i = a[m + 1]; i <= a[m + 1] + t - 1;
            i++) //在跳过桥后所有位置中找一个最小值
        ans = min(ans, f[i]);
    cout << ans << endl;
}
int main() {
    cin >> L >> s >> t >> m;
    ans = 0;
    a[0] = 0;
    a[m + 1] = L;
    for (int i = 1; i <= m; i++) cin >> a[i];
    sort(a + 1, a + m +
         1); //对桥中间石子位置排序，这上步必须要有
    if (s == t) { //这种情况只需考查石子是否是石子的倍数即可
        for (int i = 1; i <= m; i++)
            if (a[i] % s == 0)
                ans++;
        cout << ans << endl;
    } else
        solve();
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 412KB, 提交时间: 2022-05-04

#include<iostream>
#include<algorithm>  //排序和求最小值要用到此文件。
using namespace std;
int L,s,t,m,ans;
int a[110];  //保存石子位置 
int f[11000]={0};  //f[x]表示青蛙跳到位置i最少踏的石子数 
int stone[11000]={0}; //stone[x]表示位置x是否是石子，0表示不是，1表示是 
void solve()
{
    int d(0),k=s*t,x;  //d表示累加平移量，k表示s和t的公倍数 
    for (int i=1;i<=m+1;i++) 
    {
        x=a[i]-d-a[i-1];  //x表示第i个石子和第i-1个石子的距离 
        if (x>k) d+=x-k;  //超过公倍数部分用作平移 
        a[i]=a[i]-d;
        stone[a[i]]=1;  //标记平移后位置是石子 
    }
    stone[a[m+1]]=0; //桥尾不是石子 
    f[0]=0; 
    for (int i=1;i<=a[m+1]+t-1;i++)  //考查桥上到桥尾的所有位置 
    {
        f[i]=105;   
        for (int j=s;j<=t;j++) //在i的前一个位置中找一个经历石子最少的 
           if (i>=j) f[i]=min(f[i],f[i-j]);
        f[i]+=stone[i];  //加上当前位置石子数 
    }
    ans=101;
    for (int i=a[m+1];i<=a[m+1]+t-1;i++)  //在跳过桥后所有位置中找一个最小值 
        ans=min(ans,f[i]);
    cout<<ans<<endl;  
}
int main()
{
    cin>>L>>s>>t>>m;
    ans=0;
    a[0]=0; a[m+1]=L;
    for (int i=1;i<=m;i++) cin>>a[i];
    sort(a+1,a+m+1);  //对桥中间石子位置排序，这上步必须要有 
    if (s==t) {  //这种情况只需考查石子是否是石子的倍数即可 
        for (int i=1;i<=m;i++) 
            if (a[i]%s==0) 
                ans++;
        cout<<ans<<endl;   
    }
    else solve();
    return 0;
}

//http://www.cppblog.com/powerwater/articles/187391.html

C++ 解法, 执行用时: 3ms, 内存消耗: 420KB, 提交时间: 2022-06-17

#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+9;
int h[N],s,t,n,l,a[N],dp[N];
int main()
{
	cin>>l>>s>>t>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int len=s*t,dis=0;
	sort(a+1,a+n+1);
	if(s==t){
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			if(a[i]%t==0) ans++; 
		}
		cout<<ans;
		return 0;
	}
	for(int i=1;i<=n;i++){
		int l=a[i]-a[i-1];
		l=min(l,len);
		dis+=l;
		h[dis]=1;
	}
	for(int i=dis;i>=0;i--)
	{
		dp[i]=1e6;
		for(int j=s;j<=t;j++){
			dp[i]=min(dp[i],dp[j+i]+h[i]);
		}
	}
	cout<<dp[0];
}

详情