程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> URAL 1998 The old Padawan

URAL 1998 The old Padawan

編輯：C++入門知識

題目只給了500ms，注意超時問題，一開始的幾發都超時了，後來想到了預處理，從後往前推即可，為了防止t的大小可能有問題，所以進行了排序，還有人用二分做的，比較犀利先貼一個我的思路

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-7

#define inf 0xfffffff
const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;
//

int n,m,k;

int w[100000 + 5];
int t[100000 + 5];
int sum[100000 * 2];//當前往前面第一次超過k的石頭和
int step[100000 * 2];//當前往前需要回頭幾步

void clear() {
	memset(w,0,sizeof(w));
	memset(t,0,sizeof(t));
	memset(sum,0,sizeof(sum));
	memset(step,0,sizeof(step));
}

void init() {
	sum[n] = w[n];
	int tempn = n - 1;
	int cnt = 1;
	while(sum[n] <= k && tempn >=1) {//最後一個要單獨拎出來
		cnt++;
		sum[n] += w[tempn--];
	}
	step[n] = cnt;
	int tmpn = n - 1;
	while(tmpn) {
		sum[tmpn] = sum[tmpn + 1] - w[tmpn + 1];
		cnt--;
		while(sum[tmpn] <=k &&tempn >= 1) {
			cnt++;
			sum[tmpn] += w[tempn--];
		}
		step[tmpn] = cnt;
		if(tempn <= 0) {
			for(int i=tmpn;i>0;i--)//前面和已經無法超過k，所以退到直至第一次為止
				step[i] = i;
			break;
		}
		tmpn--;
	}
}

int main() {
	while(scanf("%d %d %d",&n,&m,&k) == 3) {
		clear();
		for(int i=1;i<=n;i++)
			scanf("%d",&w[i]);
		for(int i=1;i<=m;i++)
			scanf("%d",&t[i]);
		sort(t + 1,t + m + 1);
		init();
		int ans = 0;
		int mark = 0;
		for(int i=1;i<=m;i++) {
			int cha = (t[i] - t[i-1]);
			mark += cha;
			if(mark > n) {
				mark -= cha;
				break;
			}
			ans += cha;
			mark = mark - 1 - step[mark - 1];
		}
		ans += n - mark;
		printf("%d\n",ans);
	}
	return EXIT_SUCCESS;
}

/*

5 2 4

1
2

3

4

5

4

5


5 2 4

3

2

3

4

5

3

4


*/

接下來是二分做的，

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 100010
int a[N],t[N],sum[N],n,m,k,ans;
int find(int x)
{
	int l=0,r=n,res=0;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(sum[mid]